>can run in <5ms
good day
#include <stdio.h>
#include <string.h>
#define MAX_DEV 17576+1
#define MAX_OUT 21
#define OUT 10003+1
#define SVR 12731+1
#define DAC 2030+1
#define FFT 3529+1
#define findAndShadow(ret, idx, trg) \
{ \
int vis[MAX_DEV] = {0}; \
ret = findPaths(dev, vis, idx, trg); \
}
static inline int getIdx(char c1, char c2, char c3){
return 676*(c1-'a')+26*(c2-'a')+(c3-'a')+1;
}
static inline long findPaths(int dev[MAX_DEV][MAX_OUT], int vis[MAX_DEV], int idx, int trg){
long ret = 0;
if(idx == trg) return 1;
vis[idx] = -1;
if(!dev[idx][0]) return 0;
for(int i = 0; dev[idx][i] != -1; i++){
if(!vis[dev[idx][i]]) ret += findPaths(dev, vis, dev[idx][i], trg);
else if(vis[dev[idx][i]] != -1) ret += vis[dev[idx][i]];
}
if(ret) vis[idx] = ret;
return ret;
}
int main(){
char buf[MAX_OUT*4+1] = {0}, c1=0, c2=0, c3=0;
int dev[MAX_DEV][MAX_OUT] = {0};
long dto = 0, fto = 0, dtf = 0, ftd = 0, std = 0, stf = 0;
for(int i = 0; i < MAX_DEV && scanf("%c%c%c: ", &c1, &c2, &c3) != EOF; i++){
fgets(buf, MAX_OUT*4+1, stdin);
int idx = getIdx(c1, c2, c3), j = 1;
char *tok = strtok(buf, " ");
dev[idx][0] = getIdx(tok[0], tok[1], tok[2]);
for(j = 1; j < MAX_OUT && (tok = strtok(NULL, " ")) != NULL; j++){
dev[idx][j] = getIdx(tok[0], tok[1], tok[2]);
}
dev[idx][j] = -1;
}
findAndShadow(fto, FFT, OUT)
findAndShadow(dto, DAC, OUT)
findAndShadow(ftd, FFT, DAC)
findAndShadow(dtf, DAC, FFT)
findAndShadow(std, SVR, DAC)
findAndShadow(stf, SVR, FFT)
printf("%ld\n", stf*ftd*dto + std*dtf*fto);
}
