oj.uz

Submission #409412

# Submission time Handle Problem Language Result Execution time Memory
409412 2021-05-20T16:46:20 Z rqi Toy Train (IOI17_train) C++14
16 / 100
 832 ms 2220 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;

const int MOD = 1e9+7;

#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define bk back()

#define all(x) begin(x), end(x)

const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
vi radj[mx];

int to_in[mx];
int to_out[mx];

bool visited[mx];
vi order;

void dfs1(int node){
	if(a[node] == 0 || r[node] == 1) return;
	for(auto u: adj[node]){
		if(!visited[u]){
			visited[u] = 1;
			dfs1(u);
		}
	}
	order.pb(node);
}

vector<vi> comps;
vi comp;

void dfs2(int node){
	if(a[node] == 0 || r[node] == 1) return;
	comp.pb(node);
	for(auto u: radj[node]){
		if(!visited[u]){
			visited[u] = 1;
			dfs2(u);
		}
	}
}

void reduceAStrong(){ 
	//create new adj, remove self edges for AN
	for(int i = 0; i < n; i++){
		visited[i] = 0;
	}
	for(int i = 0; i < n; i++){
		if(!visited[i]){
			visited[i] = 1;
			dfs1(i);
		}
	}
	for(int i = 0; i < n; i++){
		visited[i] = 0;
	}
	reverse(all(order));
	for(auto u: order){
		if(!visited[u]){
			comp.clear();
			visited[u] = 1;
			dfs2(u);
			comps.pb(comp);
		}
	}

	for(int i = 0; i < n; i++){
		adj[i].clear();
		radj[i].clear();
	}

	for(auto COMP: comps){
		for(int i = 0; i < sz(COMP); i++){
			to_in[COMP[i]] = COMP[0];
			to_out[COMP[i]] = COMP.bk;
			if(i+1 < sz(COMP)){
				adj[COMP[i]].pb(COMP[i+1]);
			}
		}
	}

	for(int i = 0; i < m; i++){
		int A = u[i];
		int B = v[i];
		if(a[A] == 1 && r[A] == 0){
			A = to_out[A];
		}
		if(a[B] == 1 && r[B] == 0){
			B = to_in[B];
		}

		if(A == B && (a[A] == 1 && r[A] == 0)){ //remove self edge
			continue;
		}
		adj[A].pb(B);
	}

	for(int i = 0; i < n; i++){
		for(auto u: adj[i]){
			radj[u].pb(i);
		}
	}

}

array<bool, mx> dp;
array<bool, mx> ndp;

bool bad[mx];
int cur_deg[mx]; //for A

vi who_wins(vi _a, vi _r, vi _u, vi _v) {
	a = _a;
	r = _r;
	u = _u;
	v = _v;
	n = sz(a);
	m = sz(u);
	for(int i = 0; i < m; i++){
		adj[u[i]].pb(v[i]);
		radj[v[i]].pb(u[i]);
	}
	reduceAStrong();

	queue<int> q;

	for(int i = 0; i < n; i++){
		dp[i] = 1;
		if(r[i] == 1) dp[i] = 0;
	}
	for(int rep = 0; rep < mx; rep++){
		for(int i = 0; i < n; i++){
			ndp[i] = 0;
		}
		for(int i = 0; i < n; i++){
			if(r[i] == 1) continue;
			if(a[i] == 1){
				ndp[i] = 1;
				for(auto u: adj[i]){
					if(dp[u] == 0) ndp[i] = 0;
				}
			}
			else{
				ndp[i] = 0;
				for(auto u: adj[i]){
					if(dp[u] == 1) ndp[i] = 1;
				}
			}
		}
		swap(dp, ndp);
	}
	for(int i = 0; i < n; i++){
		cur_deg[i] = sz(adj[i]);
		if(dp[i] == 1){
			q.push(i);
			bad[i] = 1;
		}
	}
	while(sz(q)){
		int node = q.front();
		q.pop();
		for(auto u: radj[node]){
			if(bad[u]) continue;
			if(a[u] == 1){
				cur_deg[u]--;
				if(cur_deg[u] == 0){
					bad[u] = 1;
					q.push(u);
				}
			}
			else{
				bad[u] = 1;
				q.push(u);
			}
		}
	}

	vi ans(n, 0);
	for(int i = 0; i < n; i++){
		if(!bad[i]){
			ans[i] = 1;
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1356 KB Output is correct
2 Correct 198 ms 1384 KB Output is correct
3 Correct 203 ms 1356 KB Output is correct
4 Correct 200 ms 1356 KB Output is correct
5 Correct 199 ms 1348 KB Output is correct
6 Correct 197 ms 1348 KB Output is correct
7 Correct 180 ms 1200 KB Output is correct
8 Correct 187 ms 1420 KB Output is correct
9 Correct 203 ms 1328 KB Output is correct
10 Correct 216 ms 1296 KB Output is correct
11 Correct 159 ms 1284 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 556 KB Output is correct
2 Correct 41 ms 560 KB Output is correct
3 Correct 42 ms 544 KB Output is correct
4 Correct 41 ms 540 KB Output is correct
5 Incorrect 41 ms 548 KB 3rd lines differ - on the 3rd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 1548 KB Output is correct
2 Correct 526 ms 1644 KB Output is correct
3 Correct 723 ms 1732 KB Output is correct
4 Correct 477 ms 1744 KB Output is correct
5 Correct 674 ms 1860 KB Output is correct
6 Correct 528 ms 1728 KB Output is correct
7 Correct 554 ms 1732 KB Output is correct
8 Correct 602 ms 1684 KB Output is correct
9 Correct 116 ms 1612 KB Output is correct
10 Correct 196 ms 1756 KB Output is correct
11 Correct 132 ms 1748 KB Output is correct
12 Correct 204 ms 1768 KB Output is correct
13 Correct 788 ms 1760 KB Output is correct
14 Correct 567 ms 1732 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 1836 KB Output is correct
2 Correct 356 ms 2136 KB Output is correct
3 Correct 569 ms 1956 KB Output is correct
4 Correct 391 ms 1840 KB Output is correct
5 Correct 65 ms 556 KB Output is correct
6 Correct 216 ms 1408 KB Output is correct
7 Correct 374 ms 1484 KB Output is correct
8 Incorrect 499 ms 1612 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1356 KB Output is correct
2 Correct 198 ms 1384 KB Output is correct
3 Correct 203 ms 1356 KB Output is correct
4 Correct 200 ms 1356 KB Output is correct
5 Correct 199 ms 1348 KB Output is correct
6 Correct 197 ms 1348 KB Output is correct
7 Correct 180 ms 1200 KB Output is correct
8 Correct 187 ms 1420 KB Output is correct
9 Correct 203 ms 1328 KB Output is correct
10 Correct 216 ms 1296 KB Output is correct
11 Correct 159 ms 1284 KB Output is correct
12 Correct 42 ms 556 KB Output is correct
13 Correct 41 ms 560 KB Output is correct
14 Correct 42 ms 544 KB Output is correct
15 Correct 41 ms 540 KB Output is correct
16 Incorrect 41 ms 548 KB 3rd lines differ - on the 3rd token, expected: '0', found: '1'
17 Halted 0 ms 0 KB -