Submission #255560

#TimeUsernameProblemLanguageResultExecution timeMemory
255560HeheheToy Train (IOI17_train)C++14
100 / 100
424 ms1536 KiB
#include "train.h" #include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<long double, long double> #define sz(x) (int)((x).size()) const int N = 5e3 + 11; int n, m; int ok[N], DEG[N], deg[N], a[N], r[N], viz[N], station[N], prv[N], flag; vector<int>adj[N]; void bfs(){ for(int i = 0; i < n; i++){ viz[i] = 0; prv[i] = ok[i]; station[i] = 0; deg[i] = DEG[i]; } queue<int>q; for(int i = 0; i < n; i++){ if(!ok[i] || !r[i])continue; for(auto it : adj[i]){ if(viz[it])continue; if(a[it] || !(--deg[it])){ viz[it] = 1; q.push(it); } } station[i] = 1; } for(int i = 0; i < n; i++)ok[i] = 0; while(!q.empty()){ int i = q.front(); q.pop(); ok[i] = 1; if(station[i])continue; for(auto it : adj[i]){ if(viz[it])continue; if(a[it] || !(--deg[it])){ viz[it] = 1; q.push(it); } } } int fl = 0; for(int i = 0; i < n; i++){ if(ok[i] != prv[i])fl = 1; } if(!fl)flag = 1; } vector<int> who_wins(vector<int> A, vector<int> R, vector<int> u, vector<int> v){ n = sz(A); m = sz(u); for(int i = 0; i < n; i++){ r[i] = R[i]; a[i] = A[i]; } for(int i = 0; i < m; i++){ adj[v[i]].push_back(u[i]); } for(int i = 0; i < n; i++){ for(auto it : adj[i]){ DEG[it]++; } } memset(ok, 1, sizeof(ok)); for(int i = 0; i < n && !flag; i++){ bfs(); } vector<int> res; for(int i = 0;i < n; i++){ res.push_back(ok[i]); } 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...