oj.uz

Submission #790270

# Submission time Handle Problem Language Result Execution time Memory
790270 2023-07-22T13:54:31 Z Valaki2 Toy Train (IOI17_train) C++14
11 / 100
 229 ms 1732 KB 
#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) {
	if(charge[cur]) {
		return;
	}
	vis[cur] = true;
	for(int nei : g[cur]) {
		if(!vis[nei]) {
			dfs_1(nei);
		}
	}
	top.pb(cur);
}

void dfs_2(int cur) {
	if(charge[cur]) {
		return;
	}
	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 58 ms 1140 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1620 KB Output is correct
2 Correct 123 ms 1524 KB Output is correct
3 Correct 125 ms 1492 KB Output is correct
4 Incorrect 210 ms 1504 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1268 KB Output is correct
2 Correct 47 ms 1552 KB Output is correct
3 Correct 201 ms 1620 KB Output is correct
4 Correct 229 ms 1652 KB Output is correct
5 Correct 76 ms 1684 KB Output is correct
6 Correct 48 ms 1620 KB Output is correct
7 Correct 58 ms 1696 KB Output is correct
8 Correct 222 ms 1608 KB Output is correct
9 Correct 41 ms 1508 KB Output is correct
10 Correct 14 ms 1620 KB Output is correct
11 Correct 14 ms 1584 KB Output is correct
12 Correct 14 ms 1620 KB Output is correct
13 Correct 131 ms 1732 KB Output is correct
14 Correct 55 ms 1620 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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