| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 901926 |
2024-01-10T04:21:58 Z |
nightfal |
Toy Train (IOI17_train) |
C++14 |
|
138 ms |
262144 KB |
#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 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;
}
}
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 (now==dest) return true;
else if (dis[now]) return false;
for(int i=0; i<adjL[now].size(); i++)
if(dfs3(adjL[now][i],dest,adjL,dis,ans)) {ans[i]=1; return true;}
return false;
}
vector<int> subtask3(vector<int>& a, vector<int>& r, vector<int>& u, vector<int>& v) {
int n=a.size(), m=u.size();
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 List\n"); printAdjList(adjL);
// printf("Adjacency List Reverse\n"); printAdjList(adjLRev);
vector<int> ans(n), dis(n);
queue<int> q;
for(int i=0; i<n; i++) {
dis.assign(n,0);
if(r[i]) {
adjL.push_back(adjL[i]);
// printf("Adjacency List\n"); printAdjList(adjL);
ans[i] = (int) dfs3(n,i,adjL,dis,ans);
}
}
// return ans;
// for(int i=0; i<n; i++) printf("ans[%d]=%d ",i,ans[i]); printf("\n");
for(int i=0; i<n; i++) if(ans[i]) {q.push(i);} // cout << "push: " << i << endl;}
for(int i=0; !q.empty(); i++) {
int node = q.front(); q.pop();
for(int elem: adjLRev[node])
if (ans[elem]==0) {ans[elem] = 1; q.push(elem);} // cout << "push: " << elem << endl;}
}
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,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 (isSubtask3(a)) return subtask3(a,r,u,v);
// 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 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 dfs(int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
train.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | 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:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if (i==adjL[now].size()) ans[now] = 1;
| ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'bool dfs3(int, int, const std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
train.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0; i<adjL[now].size(); i++)
| ~^~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> subtask2(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
train.cpp:155:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(j=0; j<adjL[i].size(); j++)
| ~^~~~~~~~~~~~~~~
train.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | if (j<adjL[i].size()) {ans[i] = 1;} // printf("ans[%d]=%d\n",i,ans[i]);}
| ~^~~~~~~~~~~~~~~
train.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(j=0; j<adjL[i].size(); j++)
| ~^~~~~~~~~~~~~~~
train.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | 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:181:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
181 | 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 |
35 ms |
98896 KB |
Output is correct |
| 2 |
Correct |
35 ms |
98896 KB |
Output is correct |
| 3 |
Correct |
35 ms |
98820 KB |
Output is correct |
| 4 |
Correct |
36 ms |
98812 KB |
Output is correct |
| 5 |
Correct |
36 ms |
98896 KB |
Output is correct |
| 6 |
Correct |
36 ms |
98888 KB |
Output is correct |
| 7 |
Correct |
46 ms |
98892 KB |
Output is correct |
| 8 |
Runtime error |
138 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
3rd lines differ - on the 3rd token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
129 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
856 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 |
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 |
Correct |
35 ms |
98896 KB |
Output is correct |
| 2 |
Correct |
35 ms |
98896 KB |
Output is correct |
| 3 |
Correct |
35 ms |
98820 KB |
Output is correct |
| 4 |
Correct |
36 ms |
98812 KB |
Output is correct |
| 5 |
Correct |
36 ms |
98896 KB |
Output is correct |
| 6 |
Correct |
36 ms |
98888 KB |
Output is correct |
| 7 |
Correct |
46 ms |
98892 KB |
Output is correct |
| 8 |
Runtime error |
138 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
