#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;
void printAdjMatrix(vector<vector<int>>& adjM) {
int n = adjM.size();
for(int i=0; i<n; i++) {
printf("%d:",i);
for(int elem: adjM[i])
printf(" %d",elem);
printf("\n");
}
}
void printAdjList(vector<vector<int>>& adjL) {
int n = adjL.size();
for(int i=0; i<n; i++) {
printf("%d:",i);
for(int elem: adjL[i])
printf(" %d", elem);
printf("\n");
}
}
void printDegree(vector<int>& Deg) {
int n = Deg.size();
for(int i=0; i<n; i++) printf("Deg[%d]=%d ",i,Deg[i]);
printf("\n");
}
bool isSubtask1(vector<int>& u, vector<int>& v) {
int m = u.size();
for(int i=0; i<m; i++)
if (v[i]!=u[i] && v[i]!=u[i]+1) return false;
return true;
}
bool isSubtask2(const int n) { return n <= 15;}
bool isSubtask3(const vector<int>& a) {
for(int i=0; i<a.size(); i++)
if(a[i]==0) return false;
return true;
}
bool isSubtask4(const vector<int>& a) {
for(int i=0; i<a.size(); i++)
if(a[i]) return false;
return true;
}
bool dfs(int now, int dest, vector<int>& a, vector<int>& r, vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans) {
// printf("now:%d, dest:%d, dis[%d]=%d, r[%d]=%d, ans[%d]=%d\n",now,dest,now,(int) dis[now],now,r[now],now,ans[now]);
if (now==dest) return true;
if (dis[now]) return false;
else dis[now] = 1;
if (a[now]) {
for(int i=0; i<adjL[now].size(); i++)
if(dfs(adjL[now][i],dest,a,r,adjL,dis,ans)) {ans[now]=1; break;}
}
else {
int i;
for(i=0; i<adjL[now].size(); i++)
if(!dfs(adjL[now][i],dest,a,r,adjL,dis,ans)) break;
if (i==adjL[now].size()) ans[now] = 1;
}
if (ans[now]) printf("win %d \n",now);
return ans[now];
}
void checkNeighbor(int now, vector<int>& a, vector<vector<int>>& adjL, vector<int>& ans) {
if (a[now]) {
for(int i=0; i<adjL[now].size(); i++)
if(ans[adjL[now][i]]) ans[now]=1;
}
else {
int i;
for(i=0; i<adjL[now].size(); i++)
if(!ans[adjL[now][i]]) break;
if (i==adjL[now].size()) ans[now] = 1;
}
}
void dfs3(const int now, const int dest, const vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans) {
// printf("now:%d dest:%d\n",now,dest);
if (dis[now]) return;
dis[now] = 1;
if (now==dest) {ans[dest] = 1; /* printf("ans[%d]=%d\n",dest,ans[dest]);*/ return;}
for(int i=0; i<adjL[now].size(); i++)
dfs3(adjL[now][i],dest,adjL,dis,ans);
return;
}
// bool dfs3(const int now, const int dest, const vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans) {
// // printf("now:%d dest:%d\n",now,dest);
// if (dis[now]) return false;
// dis[now] = 1;
// if (now==dest) return true;
// for(int i=0; i<adjL[now].size(); i++)
// if(dfs3(adjL[now][i],dest,adjL,dis,ans)) return true; // {ans[now]=1; return true;}
// return false;
// }
// bool dfs4(const int now, const int dest, const vector<vector<int>>& adjL, vector<int>& dis, vector<int>& fin, vector<int>& ans) {
// // printf("now:%d dest:%d\n",now,dest);
// if (fin[now]) return ans[now];
// if (now==dest) return true;
// if (dis[now]) return false;
// dis[now] = 1;
// for(int i=0; i<adjL[now].size(); i++)
// if(!dfs4(adjL[now][i],dest,adjL,dis,fin,ans)) {fin[now]=1; ans[now]=0;/* printf("ans[%d]=%d\n",now,ans[now]);*/ return false;}
// fin[now]=1; ans[now]=1; return true;
// }
vector<int> subtask4(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
// printf("subtask4\n");
int n=a.size(), m=u.size();
vector<vector<int>> adjL(n+1), adjLRev(n+1);
for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}
vector<int> ans(n), cnt(n), ans2(n);
queue<int> q;
for(int i=0; i<n; i++) if(r[i]) {ans[i]=1;} // cout << "push: " << i << endl;}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) if (ans[j]==1) q.push(j);
cnt.assign(n,0); ans2.assign(n,0);
while(!q.empty()) {
int node = q.front(); q.pop();
for(int elem: adjLRev[node])
if (++cnt[elem]==adjL[elem].size()) {
ans2[elem]=1;
if(!ans[elem]) q.push(elem);
// printf("ans2[%d]=1 ", elem); cout << "push: " << elem << endl;
}
}
// for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n");
// for(int j=0; j<n; j++) printf("ans2[%d]=%d ",j,ans2[j]); printf("\n\n");
bool update=false;
for(int j=0; j<n; j++) if(ans[j]&&!ans2[j]) {ans[j] = 0; update=true;}
// printf(update? "yes\n":"no\n");
// for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n");
if (!update) return ans2;
}
cnt.assign(n,0);
for(int i=0; i<n; i++) if(ans[i]) {q.push(i);} // cout << "push: " << i << endl;}
while(!q.empty()) {
// for(int j=0; j<n; j++) printf("ans [%d]=%d ",j,ans[j]); printf("\n");
int node = q.front(); q.pop();
for(int elem: adjLRev[node])
if (ans[elem]==0 && ++cnt[elem]==adjL[elem].size()) {ans[elem]=1; q.push(elem);} // cout << "push: " << elem << endl;}
}
return ans;
}
// vector<int> subtask4(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
// // printf("subtask4\n");
// int n=a.size(), m=u.size();
// vector<vector<int>> adjL(n+1), adjLRev(n+1);
// for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}
// vector<int> ans(n), cnt(n);
// // dis(n+1), fin(n+1);
// for(int i=0; i<n; i++) {
// if(r[i]) {
// // dis.assign(n+1,0);
// // fin.assign(n+1,0);
// cnt.assign(n,0);
// adjLRev[n] = adjLRev[i];
// // printf("Adjacency List\n"); printAdjList(adjL);
// // printf("Adjacency List Reverse\n"); printAdjList(adjLRev);
// // printf("i=%d\n",i);
// queue<int> q; q.push(n);
// while(!q.empty()){
// int node = q.front(); q.pop();
// // printf("node=%d\n",node);
// // if (node == i) {ans[i] = 1; break;}
// for(int elem: adjLRev[node]) {
// // printf("elem=%d ",elem);
// if(++cnt[elem]==adjL[elem].size()) {
// if (elem==i) {ans[i]=1; break;}
// else q.push(elem);
// }
// }
// }
// while(!q.empty()) q.pop();
// // dfs4(n,i,adjL,dis,fin,ans);
// }
// }
// // return ans;
// printf("\n"); for(int i=0; i<n; i++) printf("ans[%d]=%d ",i,ans[i]); printf("\n");
// queue<int> q; cnt.assign(n,0);
// for(int i=0; i<n; i++) if(ans[i]) {q.push(i);} // cout << "push: " << i << endl;}
// while(!q.empty()) {
// int node = q.front(); q.pop();
// for(int elem: adjLRev[node])
// if (ans[elem]==0 && ++cnt[elem]==adjL[elem].size()) {ans[elem]=1; q.push(elem);} // cout << "push: " << elem << endl;}
// }
// return ans;
// }
vector<int> subtask3(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
// printf("subtask3\n");
int n=a.size(), m=u.size();
vector<vector<int>> adjL(n+1), adjLRev(n);
for(int i=0; i<m; i++) {adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);}
vector<int> ans(n), dis(n+1);
for(int i=0; i<n; i++) {
if(r[i]) {
dis.assign(n+1,0);
adjL[n] = adjL[i];
dfs3(n,i,adjL,dis,ans);
}
}
queue<int> q;
for(int i=0; i<n; i++) if(ans[i]) q.push(i);
while(!q.empty()) {
int node = q.front(); q.pop();
for(int elem: adjLRev[node])
if (ans[elem]==0) {ans[elem]=1; q.push(elem);}
}
return ans;
}
vector<int> subtask2(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
int n=a.size(), m=u.size();
// queue<int> q;
vector<vector<int>> adjL(n), adjLRev(n), adjM(n,vector<int>(n));
vector<int> inDeg(n), outDeg(n);
for(int i=0; i<m; i++) {
adjL[u[i]].push_back(v[i]); adjLRev[v[i]].push_back(u[i]);
adjM[u[i]][v[i]] = 1;
inDeg[v[i]]++; outDeg[u[i]]++;
}
for(auto& list: adjL) sort(list.begin(),list.end());
for(auto& list: adjLRev) sort(list.begin(),list.end());
// printf("Adjacency Matrix\n"); printAdjMatrix(adjM);
// printf("Adjacency List\n"); printAdjList(adjL);
// printf("Adjacency List Reverse\n"); printAdjList(adjLRev);
// printf("outDegree\n"); printDegree(outDeg);
// printf("inDegree\n"); printDegree(inDeg);
vector<int> ans(n);
for(int i=0; i<n; i++)
if(r[i] && !ans[i]) {
vector<int> dis(n); int j;
dis[i] = 1;
if(a[i]) {
for(j=0; j<adjL[i].size(); j++)
if(dfs(adjL[i][j],i,a,r,adjL,dis,ans)) break;
if (j<adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
}
else {
for(j=0; j<adjL[i].size(); j++)
if(!dfs(adjL[i][j],i,a,r,adjL,dis,ans)) break;
if (j==adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
}
// if (ans[i]) printf("win %d \n",i);
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if (ans[j]==0) checkNeighbor(j,a,adjL,ans);
return ans;
}
vector<int> subtask1(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
int n = a.size(), m = u.size();
vector<int> ans(n);
vector<vector<int>> adj(n,vector<int>(n));
for(int i=0; i<m; i++) adj[u[i]][v[i]] = 1;
ans[n-1]=r[n-1];
for(int i=n-2; i>=0; i--)
if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}
else {ans[i] = (adj[i][i]==0 || r[i]) && (adj[i][i+1]==0 || ans[i+1]);}
return ans;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
if (isSubtask4(a)) return subtask4(a,r,u,v);
if (isSubtask3(a)) return subtask3(a,r,u,v);
if (isSubtask1(u,v)) return subtask1(a,r,u,v);
int n = a.size(), m = u.size();
vector<vector<int>> adj(n);
for(int i=0; i<m; i++) adj[u[i]].push_back(v[i]);
for(int i=0; i<n; i++) sort(adj[i].begin(),adj[i].end());
// if (isSubtask2(n)) return subtask2(a,r,u,v);
// for(int i=0; i<n; i++) {
// cout << i << ": ";
// for (const int elem: adj[i])
// cout << elem << " ";
// cout << endl;
// }
}
Compilation message
train.cpp: In function 'bool isSubtask3(const std::vector<int>&)':
train.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0; i<a.size(); i++)
| ~^~~~~~~~~
train.cpp: In function 'bool isSubtask4(const std::vector<int>&)':
train.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0; i<a.size(); i++)
| ~^~~~~~~~~
train.cpp: In function 'bool dfs(int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
train.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if (i==adjL[now].size()) ans[now] = 1;
| ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'void checkNeighbor(int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&)':
train.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:81:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (i==adjL[now].size()) ans[now] = 1;
| ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'void dfs3(int, int, const std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
train.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask4(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:129:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | if (++cnt[elem]==adjL[elem].size()) {
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
train.cpp:150:44: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | if (ans[elem]==0 && ++cnt[elem]==adjL[elem].size()) {ans[elem]=1; q.push(elem);} // cout << "push: " << elem << endl;}
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask2(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:255:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for(j=0; j<adjL[i].size(); j++)
| ~^~~~~~~~~~~~~~~
train.cpp:257:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
257 | if (j<adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
| ~^~~~~~~~~~~~~~~
train.cpp:260:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
260 | for(j=0; j<adjL[i].size(); j++)
| ~^~~~~~~~~~~~~~~
train.cpp:262:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
262 | if (j==adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
| ~^~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask1(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:281:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
281 | if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:293:30: warning: control reaches end of non-void function [-Wreturn-type]
293 | vector<vector<int>> adj(n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
98652 KB |
Output is correct |
| 2 |
Correct |
37 ms |
98640 KB |
Output is correct |
| 3 |
Correct |
39 ms |
98436 KB |
Output is correct |
| 4 |
Correct |
44 ms |
98640 KB |
Output is correct |
| 5 |
Correct |
39 ms |
98648 KB |
Output is correct |
| 6 |
Correct |
40 ms |
98492 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 9 |
Correct |
45 ms |
98488 KB |
Output is correct |
| 10 |
Correct |
38 ms |
98636 KB |
Output is correct |
| 11 |
Correct |
41 ms |
98540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
500 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1632 KB |
Output is correct |
| 2 |
Correct |
25 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
49 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
319 ms |
1624 KB |
Output is correct |
| 5 |
Correct |
42 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
71 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
239 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1368 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1368 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1488 KB |
Output is correct |
| 15 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 16 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1632 KB |
Output is correct |
| 18 |
Correct |
142 ms |
1460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1368 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1480 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
8 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
98652 KB |
Output is correct |
| 2 |
Correct |
37 ms |
98640 KB |
Output is correct |
| 3 |
Correct |
39 ms |
98436 KB |
Output is correct |
| 4 |
Correct |
44 ms |
98640 KB |
Output is correct |
| 5 |
Correct |
39 ms |
98648 KB |
Output is correct |
| 6 |
Correct |
40 ms |
98492 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1204 KB |
Output is correct |
| 9 |
Correct |
45 ms |
98488 KB |
Output is correct |
| 10 |
Correct |
38 ms |
98636 KB |
Output is correct |
| 11 |
Correct |
41 ms |
98540 KB |
Output is correct |
| 12 |
Runtime error |
1 ms |
500 KB |
Execution killed with signal 6 |
| 13 |
Halted |
0 ms |
0 KB |
- |
