Submission #424130

#TimeUsernameProblemLanguageResultExecution timeMemory
424130cfalasToy Train (IOI17_train)C++14
0 / 100
146 ms50820 KiB
#include "train.h" #include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto &v : a) #define len(x) ((int)x.size()) int c=0; vector<vi> adj; vector<vi> rev; vi vis; vector<int> path; vii loops; vector<vi> paths; void dfs(int s){ path.push_back(s); vis[s] = c; paths[s] = path; for(auto v : adj[s]){ if(!vis[v]) dfs(v); else if(vis[v]==c){ loops.push_back({s,v}); } } path.erase(path.end()-1); } vi who_wins(vi a, vi r, vi u, vi v) { int n = len(a); adj.assign(n, vi()); rev.assign(n, vi()); paths.resize(n); vis.assign(n,0); vi res(n, 0); FOR(i, len(u)){ cout<<u[i]<<" "<<v[i]<<endl; adj[u[i]].push_back(v[i]); rev[v[i]].push_back(u[i]); } FOR(i,n){ if(!vis[i]){ c++, dfs(i); } } FOA(loop, loops){ bool start = true; bool win = false; vi path; FOA(v,paths[loop.F]){ if(v==loop.S) start = true; if(start){ if(r[v]) win = true; path.push_back(v); } } if(win && !res[loop.F]){ queue<int> q; FOA(v,path) q.push(v); vi used(n, 0); while(!q.empty()){ int t = q.front(); q.pop(); res[t] = 1; FOA(v,rev[t]){ if(!used[v]){ used[v] = true; q.push(v); } } } } } return res; }
#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...