Submission #790105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790105	2023-07-22T10:35:19 Z	fatemetmhr	Toy Train (IOI17_train)	C++17	11 / 100	980 ms	25536 KB

train

//  ~ Be Name Khoda ~  //

#include "train.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int cnt[maxn5], cmp[maxn5];
int num = 0;
vector <int> adj[maxn5], jda[maxn5], ver;
bool mark[maxn5], loop[maxn5];

void dfs1(int v){
	mark[v] = true;
	for(auto u : adj[v]) if(!mark[u])
		dfs1(u);
	ver.pb(v);
}

void dfs2(int v){
	mark[v] = true;
	cmp[v] = num;
	cnt[num]++;
	for(auto u : jda[v]) if(!mark[u])
		dfs2(u);

}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = a.size(), m = u.size();
	for(int i = 0; i < m; i++){
		adj[u[i]].pb(v[i]);
		jda[v[i]].pb(u[i]);
		if(u[i] == v[i])
			loop[u[i]] = true;
	}

	for(int i = 0; i < n; i++) if(!mark[i])
		dfs1(i);
	reverse(all(ver));
	memset(mark, false, sizeof mark);
	for(auto u : ver) if(!mark[u]){
		dfs2(u);
		num++;
	}
	vector <int> ans;
	for(int i = 0; i < n; i++) if(cnt[cmp[i]] == 1 && !loop[i])
		r[i] = 0;
	for(int i = 0; i < n; i++){
		memset(mark, false, sizeof mark);
		ver.clear();
		dfs1(i);
		bool re = false;
		for(int j = 0; j < n; j++) if(r[j] && mark[j])
			re = true;
		ans.pb(re);
	}
	return ans;

}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	25440 KB	Output is correct
2	Correct	224 ms	25348 KB	Output is correct
3	Correct	212 ms	25392 KB	Output is correct
4	Correct	980 ms	25304 KB	Output is correct
5	Correct	700 ms	25292 KB	Output is correct
6	Correct	524 ms	25188 KB	Output is correct
7	Correct	562 ms	25152 KB	Output is correct
8	Correct	356 ms	25192 KB	Output is correct
9	Correct	323 ms	25164 KB	Output is correct
10	Correct	404 ms	25152 KB	Output is correct
11	Correct	353 ms	25128 KB	Output is correct
12	Correct	85 ms	25288 KB	Output is correct
13	Correct	945 ms	25508 KB	Output is correct
14	Correct	971 ms	25536 KB	Output is correct
15	Correct	952 ms	25516 KB	Output is correct
16	Correct	939 ms	25532 KB	Output is correct
17	Correct	938 ms	25508 KB	Output is correct
18	Correct	341 ms	25300 KB	Output is correct