Submission #1025860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1025860	2024-07-17T10:50:12 Z	amirhoseinfar1385	Toy Train (IOI17_train)	C++17	11 / 100	1900 ms	2904 KB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
vector<int>adj[maxn],revadj[maxn];
int n,shar[maxn],arez[maxn],m,dp[maxn],vas[maxn],dide[maxn];

void bfs(){
	vector<int>bf;
	for(int i=0;i<n;i++){
		vas[i]=0;
		if(dp[i]==1){
			bf.push_back(i);
		}
	}
	for(int u=0;u<(int)bf.size();u++){
		for(auto i:revadj[bf[u]]){
			if(vas[i]){
				continue;
			}
			vas[i]=1;
			int cnt=0;
			int f=0;
			for(auto x:adj[i]){
				if(dp[x]==1){
					cnt++;
				}
			}
			if(arez[i]){
				if(cnt>0){
					dp[i]=1;
					bf.push_back(i);
				}else{
					dp[i]=0;
				}
			}else{
				if(cnt!=(int)adj[i].size()){
					dp[i]=0;
				}else{
					dp[i]=1;
					bf.push_back(i);
				}
			}
		}
	}
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n=(int)a.size();
	m=(int)u.size();
	for(int i=0;i<=n;i++){
		adj[i].clear();
		revadj[i].clear();
		shar[i]=vas[i]=dide[i]=dp[i]=arez[i]=0;
	}
	for(int i=0;i<n;i++){
		if(a[i]){
			arez[i]=1;
		}
		if(r[i]){
			shar[i]=1;
		}
	}
	for(int i=0;i<m;i++){
		revadj[v[i]].push_back(u[i]);
		adj[u[i]].push_back(v[i]);
	}
	for(int nago=0;nago<=n;nago++){
		for(int i=0;i<n;i++){
			dp[i]=shar[i];
		}
		bfs();
	/*for(int asd=0;asd<=n;asd++){
		for(int i=0;i<n;i++){
			if(dp[i]){
				continue;
			}
			int cnt=0;
			int f=0;
			for(auto x:adj[i]){
				if(dp[x]==1){
					cnt++;
				}
			}
			if(arez[i]){
				if(cnt>0){
					dp[i]=1;
				}else{
					dp[i]=0;
				}
			}else{
				if(cnt!=(int)adj[i].size()){
					dp[i]=0;
				}else{
					dp[i]=1;
				}
			}
		}
	}*/
		if(nago!=n){
			for(int i=0;i<n;i++){
				if(shar[i]==1){
					int cnt=0;
					for(auto x:adj[i]){
						if(dp[x]==1){
							cnt++;
						}
					}
					if(arez[i]){
						shar[i]=(cnt>=1);
					}else{
						shar[i]=(cnt==(int)adj[i].size());
					}
				}
			}
		}
	}
	vector<int>res(n);
	for(int i=0;i<n;i++){
		res[i]=dp[i];
	}
	return res;
}

Compilation message

train.cpp: In function 'void bfs()':
train.cpp:23:8: warning: unused variable 'f' [-Wunused-variable]
   23 |    int f=0;
      |        ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	224 ms	2496 KB	3rd lines differ - on the 26th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	1628 KB	3rd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	2648 KB	Output is correct
2	Correct	132 ms	2848 KB	Output is correct
3	Correct	142 ms	2648 KB	Output is correct
4	Correct	1817 ms	2812 KB	Output is correct
5	Correct	455 ms	2652 KB	Output is correct
6	Correct	50 ms	2648 KB	Output is correct
7	Correct	1900 ms	2648 KB	Output is correct
8	Correct	326 ms	2776 KB	Output is correct
9	Correct	44 ms	2716 KB	Output is correct
10	Correct	503 ms	2748 KB	Output is correct
11	Correct	376 ms	2904 KB	Output is correct
12	Correct	37 ms	2652 KB	Output is correct
13	Correct	1442 ms	2808 KB	Output is correct
14	Correct	1470 ms	2812 KB	Output is correct
15	Correct	1466 ms	2812 KB	Output is correct
16	Correct	1449 ms	2804 KB	Output is correct
17	Correct	1473 ms	2648 KB	Output is correct
18	Correct	161 ms	2644 KB	Output is correct