Submission #150769

#TimeUsernameProblemLanguageResultExecution timeMemory
150769TeamSUA (#200)Bulb Game (FXCUP4_bulb)C++17
0 / 100
2 ms352 KiB
#include "bulb.h" #include <bits/stdc++.h> int ml[300010],ml2[300010]; int rc[300010],fa[300010]; bool ok[300010]; void dfs(int x, std::vector<int> &L, std::vector<int> &R) { if (L[x] > 0) { dfs(L[x], L, R); fa[L[x]] = x; rc[L[x]] = rc[x]; ml[x] = ml[L[x]]; ml2[x] = ml2[L[x]]; } else { ml[x] = L[x]; ml2[x] = x; } if (R[x] > 0) { dfs(R[x], L, R); fa[R[x]] = x; rc[R[x]] = rc[x] + 1; } } void dfs2(int x, std::vector<int> &L, std::vector<int> &R) { if (x < 0) { return; } if (x > 0) { ok[x] = ok[fa[x]]; if (x == L[fa[x]]) { ok[x] &= (ml[R[fa[x]]] == -1); } else { ok[x] &= (ml[L[fa[x]]] == -1); } } dfs2(L[x],L,R); dfs2(R[x],L,R); } int FindWinner(int T, std::vector<int> L, std::vector<int> R){ int N = L.size(); rc[0] = 0; dfs(0,L,R); ok[0] = true; dfs2(0,L,R); /* for (int i=0;i<N;i++) { printf("%d %d %d %d %d\n",i,ml[i],ml2[i],rc[i],ok[i]); } */ if (ml[0] == -2) { return 0; } puts("cnm"); for (int i=0;i<N;i++) { if (rc[i] == 1 && ml[i] == -1 && i == ml2[i] && ok[i]) { printf("find %d\n",i); return 1; } } for (int i=0;i>=0;i=L[i]) { if (ok[i] && R[i] == -1) { return 1; } } bool chain = true; for (int i=0;i<N;i++) { if (L[i] >= 0 && R[i] >= 0) { chain = false; } } if (chain) { int down = 0, step = 0; while(L[down] >= 0 && R[down] >= 0) { if (L[down] >= 0) { down = L[down]; } else { down = R[down]; step++; } } printf("fuck %d\n",step); if (step == 0) { if (ok[down]) { return 1; } } else if (step == 1) { if (ok[down] && R[down] == -1) { return 1; } } } //puts("?"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...