Submission #799777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
799777	2023-08-01T02:03:44 Z	alvingogo	Toy Train (IOI17_train)	C++14	0 / 100	134 ms	1428 KB

train

#include "train.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n=a.size(),m=u.size();
	vector<int> vis(n);
	vector<vector<int> > e(n);
	vector<int> deg(n);
	for(int i=0;i<m;i++){
		e[v[i]].push_back(u[i]);
		deg[u[i]]++;
	}
	auto find=[&](vector<int>& b,int s){
		queue<int> q;
		for(auto h:b){
			q.push(h);
		}
		vector<int> ret,v2(n);
		auto d=deg;
		while(q.size()){
			auto h=q.front();
			q.pop();
			ret.push_back(h);
			for(auto u:e[h]){
				if(!vis[u] && !v2[u]){
					if(a[u]==s){
						v2[u]=1;
						q.push(u);
					}
					else{
						d[u]--;
						if(d[u]==0){
							q.push(u);
						}
					}
				}
			}
		}
		return ret;
	};
	vector<int> ans(n);
	while(1){
		vector<int> s;
		for(int i=0;i<n;i++){
			if(!vis[i] && r[i]){
				s.push_back(i);
			}
		}
		auto x=find(s,1);
		vector<int> p(n);
		for(int i=0;i<n;i++){
			if(vis[i]){
				p[i]=1;
			}
		}
		for(auto h:x){
			p[h]=1;
		}
		vector<int> b;
		for(int i=0;i<n;i++){
			if(!p[i]){
				b.push_back(i);
			}
		}
		if(b.empty()){
			for(auto h:x){
				ans[h]=1;
			}
			break;
		}
		auto c=find(b,0);
		for(auto h:c){
			vis[h]=1;
			for(auto z:e[h]){
				deg[z]--;
			}
		}
	}
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	296 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	288 KB	Output is correct
4	Incorrect	1 ms	212 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
5	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	1412 KB	Output is correct
2	Correct	102 ms	1428 KB	Output is correct
3	Correct	134 ms	1424 KB	Output is correct
4	Correct	6 ms	1336 KB	Output is correct
5	Incorrect	6 ms	1408 KB	3rd lines differ - on the 25th token, expected: '1', found: '0'
6	Halted	0 ms	0 KB	-