제출 #137216

#제출 시각아이디문제언어결과실행 시간메모리
137216Mahdi_Jfri장난감 기차 (IOI17_train)C++14
15 / 100
16 ms4092 KiB
#include "train.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define bit(a , b) (((a)>>(b))&1) const int maxn = 5e3 + 20; map<pair<pair<int , int> , int> , bool> mp; int n , who[maxn]; bool is[maxn]; vector<int> adj[maxn] , out[maxn] , in[maxn]; int get_dp(int mask1 , int mask2 , int v) { pair<pair<int , int> , int> tmp = {{mask1 , mask2} , v}; if(mp.count(tmp)) return mp[tmp]; for(auto u : adj[v]) { int w; if(bit(mask1 , u)) w = 1; else if(bit(mask2 , u)) w = 0; else { if(is[u]) w = get_dp(mask1 | mask2 | (1 << u) , 0 , u); else w = get_dp(mask1 , mask2 | (1 << u) , u); } if(w == who[v]) { mp[tmp] = who[v]; return who[v]; } } mp[tmp] = 1 - who[v]; return 1 - who[v]; } int DFS(int v) { for(auto u : adj[v]) { int w; if(u == v) w = is[v]; else w = DFS(u); if(w == who[v]) return who[v]; } return !who[v]; } bool visited[maxn] , has[maxn] , wtf[maxn]; vector<int> topol , ver[maxn]; int C , color[maxn]; void dfs(int v) { visited[v] = 1; for(auto u : out[v]) if(!visited[u]) dfs(u); topol.pb(v); } void sfd(int v) { visited[v] = 1; color[v] = C; ver[C].pb(v); has[color[v]] |= is[v]; for(auto u : in[v]) if(!visited[u]) sfd(u); } vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { n = a.size(); bool all = 1; for(int i = 0; i < n; i++) { is[i] = r[i] , who[i] = a[i]; all &= who[i]; } bool f = 1; for(int i = 0; i < (int)u.size(); i++) { f &= (v[i] - u[i] <= 1) && (v[i] >= u[i]); adj[u[i]].pb(v[i]); out[u[i]].pb(v[i]); in[v[i]].pb(u[i]); if(v[i] == u[i]) wtf[i] = 1; } vector<int> ans; if(n <= 15) { for(int i = 0; i < n; i++) { if(is[i]) ans.pb(get_dp(1 << i , 0 , i)); else ans.pb(get_dp(0 , (1 << i) , i)); } } else if(f) { for(int i = 0; i < n; i++) ans.pb(DFS(i)); } else if(all) { for(int i = 0; i < n; i++) if(!visited[i]) dfs(i); reverse(topol.begin() , topol.end()); memset(visited , 0 , sizeof visited); for(auto v : topol) if(!visited[v]) { sfd(v); C++; } for(int i = C - 1; i >= 0; i--) for(auto v : ver[i]) for(auto u : out[v]) has[i] |= has[color[u]]; for(int i = 0; i < n; i++) ans.pb(has[color[i]]); } else { for(int i = 0; i < n; i++) if(!visited[i] && !is[i]) dfs(i); reverse(topol.begin() , topol.end()); memset(visited , 0 , sizeof visited); for(auto v : topol) if(!visited[v]) { sfd(v); has[C] = (ver[C].size() > 1) || (wtf[ver[C][0]]); C++; } for(int i = C - 1; i >= 0; i--) for(auto v : ver[i]) for(auto u : out[v]) has[i] |= has[color[u]]; for(int i = 0; i < n; i++) { if(!is[i]) is[i] = has[color[i]]; else is[i] = 0; } } return ans; }
#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...