Submission #790262

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790262	2023-07-22T13:49:33 Z	Valaki2	Toy Train (IOI17_train)	C++14	11 / 100	233 ms	1816 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int maxn = 5000;

int n, m;
vector<int> g[1 + maxn], rg[1 + maxn];
int own[1 + maxn], charge[1 + maxn];
bool has_self[1 + maxn];

bool good[1 + maxn];

vector<int> top;
int comp[1 + maxn];
bool vis[1 + maxn];
int comp_cnt;
int comp_size[1 + maxn];

void dfs_1(int cur) {
	vis[cur] = true;
	for(int nei : g[cur]) {
		if(!vis[nei]) {
			dfs_1(nei);
		}
	}
	top.pb(cur);
}

void dfs_2(int cur) {
	comp[cur] = comp_cnt;
	for(int nei : rg[cur]) {
		if(comp[nei] == 0) {
			dfs_2(nei);
		}
	}
}

void scc() {
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			dfs_1(i);
		}
	}
	reverse(top.begin(), top.end());
	for(int cur : top) {
		if(comp[cur] == 0) {
			comp_cnt++;
			dfs_2(cur);
		}
	}
	for(int i = 1; i <= n; i++) {
		comp_size[comp[i]]++;
	}
	/*for(int i = 1; i <= n; i++) {
		cout << comp[i] << " ";
	}
	cout << endl;
	for(int i = 1; i <= comp_cnt; i++) {
		cout << comp_size[i] << " ";
	}
	cout << endl;*/
	for(int i = 1; i <= n; i++) {
		if(charge[i] == 1 && (comp_size[comp[i]] != 1 || has_self[i])) {
			good[i] = true;
		}
	}
}

void mark_good() {
	for(int iter = 1; iter <= n - 1; iter++) {
		for(int i = 1; i <= n; i++) {
			if(good[i]) {
				for(int j : rg[i]) {
					good[j] = true;
				}
			}
		}
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	for(int i = 0; i < m; i++) {
		g[u[i] + 1].pb(v[i] + 1);
		rg[v[i] + 1].pb(u[i] + 1);
		if(u[i] == v[i]) {
			has_self[u[i] + 1] = true;
		}
	}
	for(int i = 1; i <= n; i++) {
		own[i] = a[i - 1];
		charge[i] = r[i - 1];
	}
	scc();
	mark_good();
	vector<int> res(n);
	for(int i = 0; i < n; i++) {
		res[i] = good[i + 1];
	}
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	61 ms	1388 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	1 ms	468 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	13 ms	1680 KB	Output is correct
2	Correct	13 ms	1636 KB	Output is correct
3	Correct	13 ms	1612 KB	Output is correct
4	Correct	215 ms	1580 KB	Output is correct
5	Correct	198 ms	1752 KB	Output is correct
6	Correct	22 ms	1620 KB	Output is correct
7	Correct	221 ms	1660 KB	Output is correct
8	Correct	122 ms	1680 KB	Output is correct
9	Correct	16 ms	1600 KB	Output is correct
10	Correct	183 ms	1632 KB	Output is correct
11	Correct	136 ms	1620 KB	Output is correct
12	Correct	21 ms	1596 KB	Output is correct
13	Correct	212 ms	1804 KB	Output is correct
14	Correct	216 ms	1804 KB	Output is correct
15	Correct	209 ms	1816 KB	Output is correct
16	Correct	225 ms	1804 KB	Output is correct
17	Correct	216 ms	1748 KB	Output is correct
18	Correct	15 ms	1364 KB	Output is correct