oj.uz

Submission #790268

# Submission time Handle Problem Language Result Execution time Memory
790268 2023-07-22T13:53:36 Z Valaki2 Toy Train (IOI17_train) C++14
0 / 100
 217 ms 1620 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 61 ms 1124 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 0 ms 468 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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