oj.uz

Submission #821823

# Submission time Handle Problem Language Result Execution time Memory
821823 2023-08-11T17:58:59 Z ttamx Toy Train (IOI17_train) C++14
28 / 100
 90 ms 1720 KB 
#include "train.h"
#include<bits/stdc++.h>

using namespace std;

const int N=5005;

int n,m;
int all;
int a[N],cnt[N];
bool vis[N],vis2[N],used[N];
vector<int> r;
vector<int> adj[N],rev[N];

vector<int> who_wins(vector<int> _a, vector<int> _r, vector<int> _u, vector<int> _v){
	n=_a.size();
	m=_u.size();
	all=n;
	for(int i=0;i<n;i++)a[i]=_a[i];
	for(int i=0;i<n;i++)if(_r[i])r.emplace_back(i);
	for(int i=0;i<m;i++){
		int u=_u[i],v=_v[i];
		adj[u].emplace_back(v);
		rev[v].emplace_back(u);
	}
	vector<int> ans(n);
	while(all>0){
		vector<int> q;
		for(int i=0;i<n;i++){
			vis[i]=false;
			cnt[i]=0;
		}
		for(auto x:r){
			if(used[x])continue;
			q.emplace_back(x);
			vis[x]=true;
		}
		for(int i=0;i<q.size();i++){
			int u=q[i];
			for(auto v:rev[u]){
				if(vis[v]||used[v])continue;
				if(a[v]){
					vis[v]=true;
					q.emplace_back(v);
				}else if(++cnt[v]==adj[v].size()){
					vis[v]=true;
					q.emplace_back(v);
				}
			}
		}
		if(q.size()==all){
			for(auto x:q){
				ans[x]=1;
				used[x]=true;
				all--;
			}
			break;
		}
		vector<int> q2;
		for(int i=0;i<n;i++){
			vis2[i]=false;
			cnt[i]=0;
		}
		for(int i=0;i<n;i++){
			if(used[i])continue;
			if(!vis[i]){
				q2.emplace_back(i);
				vis2[i]=true;
			}
		}
		for(int i=0;i<q2.size();i++){
			int u=q2[i];
			for(auto v:rev[u]){
				if(vis2[v]||used[v])continue;
				if(!a[v]){
					vis2[v]=true;
					q2.emplace_back(v);
				}else if(++cnt[v]==adj[v].size()){
					vis2[v]=true;
					q2.emplace_back(v);
				}
			}
		}
		for(auto x:q2){
			ans[x]=0;
			used[x]=true;
			all--;
		}
	}
	return ans;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0;i<q.size();i++){
      |               ~^~~~~~~~~
train.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     }else if(++cnt[v]==adj[v].size()){
      |              ~~~~~~~~^~~~~~~~~~~~~~~
train.cpp:51:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   if(q.size()==all){
      |      ~~~~~~~~^~~~~
train.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0;i<q2.size();i++){
      |               ~^~~~~~~~~~
train.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     }else if(++cnt[v]==adj[v].size()){
      |              ~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 4 ms 1196 KB Output is correct
3 Correct 8 ms 1224 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 4 ms 1200 KB Output is correct
7 Correct 3 ms 1196 KB Output is correct
8 Correct 4 ms 1236 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Incorrect 1 ms 468 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1492 KB Output is correct
2 Correct 73 ms 1708 KB Output is correct
3 Correct 90 ms 1708 KB Output is correct
4 Correct 9 ms 1584 KB Output is correct
5 Incorrect 6 ms 1620 KB 3rd lines differ - on the 11th token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1340 KB Output is correct
2 Correct 8 ms 1452 KB Output is correct
3 Correct 8 ms 1624 KB Output is correct
4 Correct 7 ms 1620 KB Output is correct
5 Correct 6 ms 1620 KB Output is correct
6 Correct 6 ms 1620 KB Output is correct
7 Correct 6 ms 1620 KB Output is correct
8 Correct 6 ms 1620 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 6 ms 1720 KB Output is correct
11 Correct 6 ms 1620 KB Output is correct
12 Correct 9 ms 1708 KB Output is correct
13 Correct 7 ms 1584 KB Output is correct
14 Correct 6 ms 1568 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1364 KB Output is correct
2 Correct 6 ms 1576 KB Output is correct
3 Correct 9 ms 1620 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 4 ms 1236 KB Output is correct
8 Correct 4 ms 1236 KB Output is correct
9 Correct 4 ms 1192 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 4 ms 1172 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 4 ms 1196 KB Output is correct
3 Correct 8 ms 1224 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 4 ms 1200 KB Output is correct
7 Correct 3 ms 1196 KB Output is correct
8 Correct 4 ms 1236 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Incorrect 1 ms 468 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
20 Halted 0 ms 0 KB -