oj.uz

Submission #409416

# Submission time Handle Problem Language Result Execution time Memory
409416 2021-05-20T16:53:57 Z rqi Toy Train (IOI17_train) C++14
39 / 100
 866 ms 2152 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){
		// cout << "COMP: ";
		// for(auto u: COMP){
		// 	cout << u << " ";
		// }
		// cout << "\n";
		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[A] == 1 && r[A] == 0) && (a[B] == 1 && r[B] == 0) && to_in[A] == to_in[B]){ //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();

	// for(int i = 0; i < n; i++){
	// 	cout << i << ": ";
	// 	for(auto u: adj[i]){
	// 		cout << u << ", ";
	// 	}
	// 	cout << "\n";
	// }

	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 191 ms 1256 KB Output is correct
2 Correct 196 ms 1264 KB Output is correct
3 Correct 232 ms 1256 KB Output is correct
4 Correct 192 ms 1376 KB Output is correct
5 Correct 201 ms 1268 KB Output is correct
6 Correct 218 ms 1264 KB Output is correct
7 Correct 193 ms 1100 KB Output is correct
8 Correct 179 ms 1344 KB Output is correct
9 Correct 196 ms 1232 KB Output is correct
10 Correct 230 ms 1228 KB Output is correct
11 Correct 207 ms 1228 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 1968 KB Output is correct
2 Correct 322 ms 2064 KB Output is correct
3 Correct 272 ms 1960 KB Output is correct
4 Correct 359 ms 1996 KB Output is correct
5 Correct 412 ms 2032 KB Output is correct
6 Correct 382 ms 1956 KB Output is correct
7 Correct 265 ms 1948 KB Output is correct
8 Correct 594 ms 2040 KB Output is correct
9 Correct 274 ms 1948 KB Output is correct
10 Correct 506 ms 1972 KB Output is correct
11 Correct 578 ms 1904 KB Output is correct
12 Correct 384 ms 2032 KB Output is correct
13 Correct 247 ms 2044 KB Output is correct
14 Correct 263 ms 2036 KB Output is correct
15 Correct 260 ms 2072 KB Output is correct
16 Correct 245 ms 2116 KB Output is correct
17 Correct 266 ms 2152 KB Output is correct
18 Correct 190 ms 1540 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1336 KB Output is correct
2 Correct 487 ms 1420 KB Output is correct
3 Correct 736 ms 1524 KB Output is correct
4 Correct 484 ms 1592 KB Output is correct
5 Correct 662 ms 1540 KB Output is correct
6 Correct 512 ms 1528 KB Output is correct
7 Correct 582 ms 1604 KB Output is correct
8 Correct 624 ms 1484 KB Output is correct
9 Correct 139 ms 1476 KB Output is correct
10 Correct 207 ms 1552 KB Output is correct
11 Correct 157 ms 1592 KB Output is correct
12 Correct 212 ms 1552 KB Output is correct
13 Correct 784 ms 1544 KB Output is correct
14 Correct 550 ms 1460 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 1628 KB Output is correct
2 Correct 293 ms 1780 KB Output is correct
3 Correct 626 ms 1700 KB Output is correct
4 Correct 365 ms 1620 KB Output is correct
5 Correct 70 ms 624 KB Output is correct
6 Correct 223 ms 1316 KB Output is correct
7 Correct 320 ms 1312 KB Output is correct
8 Correct 278 ms 1356 KB Output is correct
9 Correct 288 ms 1520 KB Output is correct
10 Correct 120 ms 816 KB Output is correct
11 Correct 291 ms 1404 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 1256 KB Output is correct
2 Correct 196 ms 1264 KB Output is correct
3 Correct 232 ms 1256 KB Output is correct
4 Correct 192 ms 1376 KB Output is correct
5 Correct 201 ms 1268 KB Output is correct
6 Correct 218 ms 1264 KB Output is correct
7 Correct 193 ms 1100 KB Output is correct
8 Correct 179 ms 1344 KB Output is correct
9 Correct 196 ms 1232 KB Output is correct
10 Correct 230 ms 1228 KB Output is correct
11 Correct 207 ms 1228 KB Output is correct
12 Correct 42 ms 536 KB Output is correct
13 Correct 42 ms 552 KB Output is correct
14 Correct 41 ms 460 KB Output is correct
15 Correct 43 ms 552 KB Output is correct
16 Incorrect 41 ms 556 KB 3rd lines differ - on the 3rd token, expected: '0', found: '1'
17 Halted 0 ms 0 KB -