oj.uz

Submission #409503

# Submission time Handle Problem Language Result Execution time Memory
409503 2021-05-21T01:22:03 Z rqi Toy Train (IOI17_train) C++14
16 / 100
 896 ms 1804 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];
bool forced[mx];
int cur_deg[mx]; //number of neighbors that can be forced into a good C
int bad_cur_deg[mx];
int self[mx];

queue<int> to_unForce;

void iForce(int node){
	for(auto u: radj[node]){
		if(forced[u]) continue;
		if(a[u] == 0){
			cur_deg[u]++;
			//cout << u << " " << cur_deg[u] << "\n";
			if(cur_deg[u] == sz(adj[u])-self[u]){
				forced[u] = 1;
				to_unForce.push(u);
			}
		}
		else{
			forced[u] = 1;
			to_unForce.push(u);
		}
	}
}

void initForce(){
	for(int i = 0; i < n; i++){
		if(r[i] == 1){
			if(!forced[i]){
				forced[i] = 1;
				to_unForce.push(i);
			}
		}
	}

	while(sz(to_unForce)){
		int node = to_unForce.front();
		to_unForce.pop();
		iForce(node);
	}

	for(int i = 0; i < n; i++){
		if(forced[i]){
			cur_deg[i] = 0;
			for(auto u: adj[i]){
				if(forced[u]){
					cur_deg[i]++;
				}
			}
		}
	}
}

queue<int> q;

void unForce(int node){
	assert(forced[node] == 0);
	//cout << "unForce " << node << "\n";
	for(auto u: radj[node]){
		if(forced[u]){
			if(a[u] == 1){
				cur_deg[u]--;
				if(cur_deg[u] == 0 || (self[u] == cur_deg[u] && r[u] == 0)){
					forced[u] = 0;
					to_unForce.push(u);

					if(!bad[u] && a[u] == 1){ //second condition unnecessary
						bad[u] = 1;
						q.push(u);
					}
				}
			}
			else{
				forced[u] = 0;
				to_unForce.push(u);
			}
			
		}
	}
}

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]);
	}
	for(int i = 0; i < n; i++){
		for(auto u: adj[i]){
			if(u == i){
				self[i]++;
			}
		}
	}

	initForce();

	//cout << "cur_deg[2]: " << cur_deg[2] << "\n";

	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++){
	// 	cout << i << " " << forced[i] << " " << cur_deg[i] << "\n";
	// }

	
	for(int i = 0; i < n; i++){
		bad_cur_deg[i] = sz(adj[i]);
		if(dp[i] == 1){
			q.push(i);
			bad[i] = 1;
			//cout << "initial bad: " << i << "\n";
		}
	}

	for(int i = 0; i < n; i++){
		if(!forced[i] && !bad[i] && a[i] == 1){ //second condition unnecessary
			q.push(i);
			bad[i] = 1;
			//cout << i << "\n";
			
		}
	}
	
	while(true){
		while(sz(to_unForce)){
			int node = to_unForce.front();
			to_unForce.pop();
			unForce(node);
		}

		if(sz(q) == 0) break;
		int node = q.front();
		q.pop();

		for(auto u: radj[node]){
			if(bad[u]) continue;
			if(a[u] == 1){
				bad_cur_deg[u]--;
				
				if(bad_cur_deg[u] == 0){
					bad[u] = 1;
					q.push(u);
				}
			}
			else{
				bad[u] = 1;
				q.push(u);
			}
		}

		if(forced[node]){
			forced[node] = 0;
			to_unForce.push(node);
		}
		
	}

	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 202 ms 1228 KB Output is correct
2 Correct 214 ms 1268 KB Output is correct
3 Correct 202 ms 1228 KB Output is correct
4 Correct 202 ms 1276 KB Output is correct
5 Correct 203 ms 1260 KB Output is correct
6 Correct 201 ms 1268 KB Output is correct
7 Correct 203 ms 1252 KB Output is correct
8 Correct 185 ms 1252 KB Output is correct
9 Correct 205 ms 1348 KB Output is correct
10 Correct 202 ms 1228 KB Output is correct
11 Correct 184 ms 1208 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 42 ms 556 KB Output is correct
3 Correct 42 ms 560 KB Output is correct
4 Correct 42 ms 560 KB Output is correct
5 Incorrect 41 ms 560 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 352 ms 1704 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 113 ms 1484 KB Output is correct
2 Correct 521 ms 1524 KB Output is correct
3 Correct 779 ms 1644 KB Output is correct
4 Correct 497 ms 1664 KB Output is correct
5 Correct 723 ms 1732 KB Output is correct
6 Correct 546 ms 1628 KB Output is correct
7 Correct 578 ms 1612 KB Output is correct
8 Correct 629 ms 1612 KB Output is correct
9 Correct 119 ms 1584 KB Output is correct
10 Correct 204 ms 1668 KB Output is correct
11 Correct 136 ms 1612 KB Output is correct
12 Correct 225 ms 1676 KB Output is correct
13 Correct 828 ms 1644 KB Output is correct
14 Correct 617 ms 1608 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 1656 KB Output is correct
2 Correct 405 ms 1796 KB Output is correct
3 Correct 706 ms 1804 KB Output is correct
4 Correct 403 ms 1664 KB Output is correct
5 Correct 65 ms 640 KB Output is correct
6 Correct 224 ms 1172 KB Output is correct
7 Correct 399 ms 1400 KB Output is correct
8 Incorrect 539 ms 1460 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 202 ms 1228 KB Output is correct
2 Correct 214 ms 1268 KB Output is correct
3 Correct 202 ms 1228 KB Output is correct
4 Correct 202 ms 1276 KB Output is correct
5 Correct 203 ms 1260 KB Output is correct
6 Correct 201 ms 1268 KB Output is correct
7 Correct 203 ms 1252 KB Output is correct
8 Correct 185 ms 1252 KB Output is correct
9 Correct 205 ms 1348 KB Output is correct
10 Correct 202 ms 1228 KB Output is correct
11 Correct 184 ms 1208 KB Output is correct
12 Correct 42 ms 556 KB Output is correct
13 Correct 42 ms 556 KB Output is correct
14 Correct 42 ms 560 KB Output is correct
15 Correct 42 ms 560 KB Output is correct
16 Incorrect 41 ms 560 KB 3rd lines differ - on the 3rd token, expected: '0', found: '1'
17 Halted 0 ms 0 KB -