제출 #575481

#제출 시각아이디문제언어결과실행 시간메모리
575481definitelynotmee장난감 기차 (IOI17_train)C++98
49 / 100
1000 ms224968 KiB
#include<bits/stdc++.h> #include"train.h" #define mp make_pair #define mt make_tuple #define all(x) x.begin(), x.end() #define ff first #define ss second using namespace std; template <typename T> using matrix = vector<vector<T>>; typedef unsigned int uint; typedef unsigned long long ull; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll INFL = (1LL<<62)-1; const int INF = (1<<30)-1; const double EPS = 1e-7; const int MOD = 1e9 + 7; const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); const int MAXN = 1e6+1; std::vector<int> whowins1cara(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { int n = a.size(), m = u.size(); matrix<int> g(n), rev(n); for(int i = 0; i < m; i++){ g[u[i]].push_back(v[i]); rev[v[i]].push_back(u[i]); } vector<int> resp(n); vector<int> degree(n); for(int i = 0; i < n; i++) degree[i] = g[i].size(); for(int v = 0; v < n; v++){ if(!r[v]) continue; vector<int> win = resp, grau = degree; auto processwin = [&](int id, auto f)->void{ for(int i : rev[id]){ if(grau[i] == 0) continue; if(a[i] == 1){ grau[i] = 0; } else grau[i]--; if(grau[i] == 0){ win[i] = 1; if(i != v) f(i,f); } } }; if(!win[v]) processwin(v,processwin); if(win[v]){ swap(resp,win); swap(grau,degree); } } return resp; } std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { int owned = accumulate(all(a),0); int recharge = accumulate(all(r),0); int n = a.size(), m = u.size(); vector<int> resp(n); matrix<int> g(n), rev(n); bool flag = 1; for(int i = 0; i < m; i++){ g[u[i]].push_back(v[i]); rev[v[i]].push_back(u[i]); flag&=v[i] == u[i] || v[i] == u[i]+1; } if(owned == n){ for(int i = 0; i < n; i++){ if(!r[i]) continue; vector<int> reach(n), reachedby(n); auto dfs =[&](int id, auto dfs)->void{ reach[id] = 1; for(int i : g[id]) if(!reach[i]) dfs(i,dfs); }; auto rdfs =[&](int id, auto dfs)->void{ reachedby[id] = 1; for(int i : rev[id]) if(!reachedby[i]) dfs(i,dfs); }; for(int j : g[i]) dfs(j,dfs); for(int j : rev[i]) rdfs(j,rdfs); if(reach[i]){ for(int j = 0; j < n; j++) resp[j]|=reachedby[j]; } } } else if(owned == 0){ for(int i = 0; i < n; i++){ if(r[i]) continue; vector<int> reach(n), reachedby(n); auto dfs =[&](int id, auto dfs)->void{ reach[id] = 1; for(int i : g[id]) if(!reach[i] && !r[i]) dfs(i,dfs); }; auto rdfs =[&](int id, auto dfs)->void{ reachedby[id] = 1; for(int i : rev[id]) if(!reachedby[i]) dfs(i,dfs); }; for(int j : g[i]) if(!r[j])dfs(j,dfs); for(int j : rev[i]) rdfs(j,rdfs); if(reach[i]){ for(int j = 0; j < n; j++) resp[j]|=reachedby[j]; } } for(int& i : resp) i^=1; } else if(flag){ for(int i = n-1; i >= 0; i--){ int t1 = 0, t2 = 0; for(int j : g[i]){ if(j == i) t1 = 1; else if(j == i+1) t2 = 1; } if(a[i]){ if(t2){ resp[i] = resp[i+1]; } if(t1 && r[i]) resp[i] = 1; } else { resp[i] = 1; if(t2){ resp[i] = resp[i+1]; } if(t1 && !r[i]) resp[i] = 0; } } } else if(recharge == 1){ return whowins1cara(a,r,u,v); } else { vector<int> power(16,1); for(int i = 1; i < 16; i++) power[i] = power[i-1]*3; matrix<char> can(n,vector<char>(power[n],-1)); auto getbit =[&](int x, int id){ return( x%(power[id]*3)-x%power[id])/power[id]; }; auto solve=[&](int id, int mask, auto solve)->int{ if(can[id][mask] != -1){ return can[id][mask]; } int resp = a[id]^1; for(int i : g[id]){ int newmask = mask; int state = getbit(mask,i); if(state == 1){ // << 'a' << '\n'; if(!a[id]){ resp = 0; break; } } else if(state == 2){ // << 'b' << '\n'; if(a[id]){ resp = 1; break; } } else { if(r[i]){ for(int j = 0; j < n; j++){ if(getbit(newmask,j) == 1){ newmask+=power[j]; } } newmask+=power[i]*2; } else { newmask+=power[i]; } // << newmask << '\n'; int cur = solve(i,newmask,solve); if(cur == a[id]){ resp = cur; break; } } } can[id][mask] = resp; return resp; }; for(int i = 0; i < n; i++){ int mask = power[i]*(1+r[i]); resp[i] = solve(i,mask,solve); } } return resp; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...