#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;
const int mod = 1e9 + 7;
const int N = 5e3 + 3;
vector < int > V[N],Y[N],iyi,kot;
int H[N],D[N],low[N],T,S[N],Z[N],own[N],R[N],ans[N],Q[N],s,z,n,i,t,hh;
void f(int x){
if(z) return;
H[x] = D[x] = low[x] = ++T;
S[++s] = x;
for(auto y : V[x]){
if(z) return;
if(ans[y] != -1) exit(0);
if(!D[y]){
f(y); low[x] = min(low[x] , low[y]);
}
else if(H[y]) low[x] = min(low[x] , D[y]);
}
if(low[x] == D[x]){
for(int y= -1; y!=x;){
y = S[s--];
Z[++z] = y;
H[y] = 0;
}
}
}
void del(int x, int y){
for(int i=0; i<V[x].size(); i++)
if(V[x][i] == y){
V[x].erase(V[x].begin() + i);
return;
}
}
void g(int x, int p, int h){
if(ans[x] != -1) return;
if(p != -1 && own[x] != h){
if(V[x].size() > 1){
del(x,p);
return;
}
}
ans[x] = h; t--;
for(auto y : Y[x]) if(ans[y] == -1) g(y,x,h);
}
vi who_wins(vi a, vi r, vi u, vi v){
t = n = a.size();
for(i=0;i<n;i++) R[i] = r[i];
for(i=0;i<n;i++) own[i] = a[i];
memset(ans,-1,sizeof ans);
for(i=0;i<u.size();i++){
V[ u[i] ].pb(v[i]);
Y[ v[i] ].pb(u[i]);
}
for(; t ;){
memset(D,0,sizeof D);
memset(low,0,sizeof low);
memset(H,0,sizeof H);
z = s = 0;
for(i=0;i<n;i++)
if(!D[i] && ans[i] == -1) f(i);
for(i=1;i<=z;i++) Q[ Z[i] ] = 1;
for(i=1;i<=z;i++)
for(auto y : V[ Z[i] ])
if(!Q[y])
exit(0);
for(i=1;i<=z;i++) Q[ Z[i] ] = 0;
for(i=1;i<=z;i++)
if(R[ Z[i] ]){
g(Z[i],-1,1);
break;
}
if(i<=z) continue;
for(i=1;i<=z;i++)
if(ans[ Z[i] ] == -1)
g(Z[i],-1,0);
}
vector < int > vv;
for(i=0;i<n;i++){
// cout << ans[i] << " ";
vv.pb(ans[i]);
}
return vv;
}
//int main(){ who_wins({0, 1}, {1, 0}, {0, 0, 1, 1}, {0, 1, 0, 1}); return 0; }
Compilation message
train.cpp: In function 'void del(int, int)':
train.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<V[x].size(); i++)
~^~~~~~~~~~~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:65:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<u.size();i++){
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
104 ms |
1528 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
1528 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
11 ms |
1692 KB |
secret mismatch |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
735 ms |
1692 KB |
3rd lines differ - on the 696th token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
1892 KB |
Output is correct |
2 |
Correct |
13 ms |
1984 KB |
Output is correct |
3 |
Incorrect |
14 ms |
1984 KB |
secret mismatch |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
104 ms |
1528 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |