oj.uz

Submission #821821

# Submission time Handle Problem Language Result Execution time Memory
821821 2023-08-11T17:58:15 Z ttamx Toy Train (IOI17_train) C++14
0 / 100
 2000 ms 1620 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(vis[v]||used[v])continue;
				if(!a[v]){
					vis[v]=true;
					q2.emplace_back(v);
				}else if(++cnt[v]==adj[v].size()){
					vis[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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 1620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 1364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -