#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 dfs(int now, int dest, vector<int>& a, vector<int>& r, vector<vector<int>>& adjL, vector<int>& dis, vector<int>& ans, int& cnt) {
// 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 (dis[now]) return r[now] || ans[now];
// else dis[now]=++cnt;
else dis[now] = 1;
if (now==dest) return true;
if (a[now]) {
for(int i=0; i<adjL[now].size(); i++)
if(dfs(i,dest,a,r,adjL,dis,ans,cnt)) {ans[now]=1; break;}
}
else {
int i;
for(i=0; i<adjL[now].size(); i++)
if(!dfs(i,dest,a,r,adjL,dis,ans,cnt)) 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;
}
}
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]==1) {
vector<int> dis(n); int cnt=0, 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,cnt)) 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,cnt)) 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,0);
vector<vector<int>> adj(n,vector<int>(n,0));
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) {
vector<int> res(a.size());
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);
if (isSubtask1(u,v)) return subtask1(a,r,u,v);
// for(int i=0; i<n; i++) {
// cout << i << ": ";
// for (const int elem: adj[i])
// cout << elem << " ";
// cout << endl;
// }
for(int i = 0; i < n; i++)
res[i] = i % 2;
return res;
}
Compilation message
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>&, int&)':
train.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | 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:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:74:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (i==adjL[now].size()) ans[now] = 1;
| ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask2(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(j=0; j<adjL[i].size(); j++)
| ~^~~~~~~~~~~~~~~
train.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if (j!=adjL[i].size()) {ans[i] = 1; /*printf("ans[%d]=%d\n",i,ans[i]);*/}
| ~^~~~~~~~~~~~~~~~
train.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(j=0; j<adjL[i].size(); j++)
| ~^~~~~~~~~~~~~~~
train.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | 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:132:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
132 | if (a[i]) {ans[i] = adj[i][i] && r[i] || adj[i][i+1] && ans[i+1];}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
98908 KB |
Output is correct |
| 2 |
Correct |
47 ms |
98996 KB |
Output is correct |
| 3 |
Correct |
39 ms |
98900 KB |
Output is correct |
| 4 |
Correct |
39 ms |
98900 KB |
Output is correct |
| 5 |
Correct |
40 ms |
98896 KB |
Output is correct |
| 6 |
Correct |
42 ms |
98920 KB |
Output is correct |
| 7 |
Correct |
39 ms |
98908 KB |
Output is correct |
| 8 |
Correct |
39 ms |
98900 KB |
Output is correct |
| 9 |
Correct |
39 ms |
98868 KB |
Output is correct |
| 10 |
Correct |
39 ms |
99020 KB |
Output is correct |
| 11 |
Correct |
39 ms |
98896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 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 |
6 ms |
1372 KB |
3rd lines differ - on the 2nd token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1116 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1372 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
98908 KB |
Output is correct |
| 2 |
Correct |
47 ms |
98996 KB |
Output is correct |
| 3 |
Correct |
39 ms |
98900 KB |
Output is correct |
| 4 |
Correct |
39 ms |
98900 KB |
Output is correct |
| 5 |
Correct |
40 ms |
98896 KB |
Output is correct |
| 6 |
Correct |
42 ms |
98920 KB |
Output is correct |
| 7 |
Correct |
39 ms |
98908 KB |
Output is correct |
| 8 |
Correct |
39 ms |
98900 KB |
Output is correct |
| 9 |
Correct |
39 ms |
98868 KB |
Output is correct |
| 10 |
Correct |
39 ms |
99020 KB |
Output is correct |
| 11 |
Correct |
39 ms |
98896 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 13 |
Halted |
0 ms |
0 KB |
- |
