Submission #600948

#TimeUsernameProblemLanguageResultExecution timeMemory
600948ArnchViruses (BOI20_viruses)C++17
0 / 100
136 ms262144 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ #include<bits/stdc++.h> //#pragma GCC optimize("O3,no-stack-protector,unroll-loops") //#pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl constexpr ll inf = 1e18, N = 1e3 + 10, mod = 1e9 + 9, pr = 1000696969; ll dp[N]; string s[N]; bool mark[N], ex[N]; map<int, bool> mp; vector<int> ind[N], val[N]; void dojob(int x) { int pos = ind[x][0]; for(auto j : val[pos]) { if(!mark[j]) dojob(j); if(ex[j]) { ex[x] = 1; break; } s[x] += s[j]; } mark[x] = 1; } int main() { ios :: sync_with_stdio(0), cin.tie(0); int g, n, m; cin >>g >>n >>m; for(int i = 0; i < n; i++) { int a, k; cin >>a >>k; for(int j = 0; j < k; j++) { int u; cin >>u; val[i].push_back(u); } ind[a].push_back(i); } for(int i = 0; i < m; i++) { int e; cin >>e; ll cur = 0; for(int j = 0; j < e; j++) { int u; cin >>u; if(u == 0) cur *= pr, cur += 1, cur %= mod; else cur *= pr, cur += 2, cur %= mod; } mp[cur] = 1; } assert(n == g - 2); s[0] = '0', s[1] = '1'; mark[0] = mark[1] = 1; for(int i = 2; i < g; i++) { if(!mark[i]) dojob(i); } for(int j = 2; j < g; j++) { if(ex[j]) { cout<<"YES" <<endl; continue; } string ans = s[j]; for(int i = 0; i < Sz(ans); i++) { ll cur = 0; bool rip = 0; for(int j = i; j < Sz(ans); j++) { cur *= pr; if(ans[j] == '0') cur += 1; else cur += 2; cur %= mod; if(mp[cur]) { rip = 1; break; } } if(rip) { cout<<"YES" <<endl; continue; } cout<<"NO" <<" " <<Sz(ans) <<endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...