#include "train.h"
#include "bits/stdc++.h"
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
using namespace std;
typedef vector<int> vi;
const int NMAX = 5010;
int N, M;
vi kind, isCharging;
vi adj[NMAX], iadj[NMAX];
bitset<NMAX> vis;
vi outdeg;
void dfs(int n){
vis[n] = 1;
for(int k : iadj[n]) if(!vis[k]) {
if(kind[k] == 1 || outdeg[k] == 1) dfs(k);
else outdeg[k]--;
}
}
vi reaches(vi start){
vi copy = outdeg;
vis.reset();
for(int n : start) if(!vis[n]) dfs(n);
outdeg = copy;
vi ret;
FOR(i, 0, N) if(vis[i]) ret.pb(i);
return ret;
}
int g[NMAX][NMAX];
vi who_wins(vi a, vi r, vi u, vi v) {
//cout<<"Called"<<endl;
kind = a;
isCharging = r;
N = a.size();
M = u.size();
outdeg.assign(N, 0);
//cout<<"starting"<<endl;
FOR(i, 0, u.size()){
adj[u[i]].pb(v[i]);
outdeg[u[i]]++;
iadj[v[i]].pb(u[i]);
}
//cout<<1<<endl;
memset(g, 0, NMAX*NMAX);
//cout<<"a "<<endl;
FOR(i, 0, N) {
vi t = reaches({i});
for(int j : t) g[i][j] = 1;
}
vi start;
//FOR(i, 0, N) {
//FOR(j, 0, N)cout<<g[i][j]<<" ";
//cout<<endl;
//}
FOR(i, 0, N) if(isCharging[i]) FOR(j, 0, N) {
if(g[i][j] and g[j][i]) {
start.pb(i);
break;
}
}
//cout << "start: " << endl;
//for(int s : start) cout << s << " ";
//cout<<endl;
//cout<<"Declaring ret"<<endl;
vi ret(N, 0);
vi out = reaches(start);
for(int k : out) ret[k] = 1;
//cout<<"returning"<<endl;
return ret;
}
/*
int main() {
int n, m;
assert(2 == scanf("%d %d", &n, &m));
vector<int> a(n), r(n), u(m), v(m);
for(int i = 0; i < n; i++)
assert(1 == scanf("%d", &a[i]));
for(int i = 0; i < n; i++)
assert(1 == scanf("%d", &r[i]));
for(int i = 0; i < m; i++)
assert(2 == scanf("%d %d", &u[i], &v[i]));
vector<int> res = who_wins(a, r, u, v);
for(int i = 0; i < (int)res.size(); i++)
printf(i ? " %d" : "%d", res[i]);
printf("\n");
return 0;
}
/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1
7 11
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 4
0 5
1 0
1 3
1 2
2 1
2 3
3 0
4 0
5 6
6 6
*/
Compilation message
train.cpp:102:1: warning: "/*" within comment [-Wcomment]
/*
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:3:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
^
train.cpp:42:2: note: in expansion of macro 'FOR'
FOR(i, 0, u.size()){
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
136 ms |
40952 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
40952 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
704 ms |
99832 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
157 ms |
99832 KB |
3rd lines differ - on the 696th token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
99832 KB |
Output is correct |
2 |
Execution timed out |
2062 ms |
99832 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
136 ms |
40952 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |