oj.uz

Submission #409512

# Submission time Handle Problem Language Result Execution time Memory
409512 2021-05-21T02:26:11 Z rqi Toy Train (IOI17_train) C++14
34 / 100
 998 ms 1876 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];
bool bad[mx];

int getBType(){
	for(int i = 0; i < n; i++){
		if(bad[i]) continue;
		if(a[i] == 1){
			bool works = 1;
			for(auto u: adj[i]){
				if(!bad[u]){
					works = 0;
					break;
				}
			}
			if(works){
				return i;
			}
		}
		else{
			for(auto u: adj[i]){
				if(bad[u]){
					return i;
				}
			}
		}
	}
	return -1;
}

array<bool, mx> dp;
array<bool, mx> ndp;
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] || bad[u]) continue;
		if(a[u] == 0){
			cur_deg[u]++;
			//cout << u << " " << cur_deg[u] << "\n";
			if(cur_deg[u] == sz(adj[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++){
		forced[i] = 0;
	}
	for(int i = 0; i < n; i++){
		if(bad[i]) continue;
		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);
	}
}

int getAType(){
	initForce();
	for(int i = 0; i < n; i++){
		if(!bad[i] && !forced[i] && a[i] == 1){
			return i;
		}
	}
	return -1;
}

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]++;
		}
	}

	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++){
		if(dp[i] == 1){
			bad[i] = 1;
			//cout << "initial bad: " << i << "\n";
		}
	}

	while(true){
		int node = getBType();
		if(node == -1){
			node = getAType();
		}
		if(node == -1) break;
		bad[node] = 1;
	}

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 528 KB Output is correct
2 Correct 42 ms 548 KB Output is correct
3 Correct 43 ms 540 KB Output is correct
4 Correct 43 ms 544 KB Output is correct
5 Correct 41 ms 552 KB Output is correct
6 Correct 42 ms 536 KB Output is correct
7 Incorrect 42 ms 532 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 1600 KB Output is correct
2 Correct 530 ms 1740 KB Output is correct
3 Correct 530 ms 1876 KB Output is correct
4 Correct 462 ms 1736 KB Output is correct
5 Correct 682 ms 1828 KB Output is correct
6 Correct 998 ms 1860 KB Output is correct
7 Correct 294 ms 1740 KB Output is correct
8 Correct 781 ms 1740 KB Output is correct
9 Correct 434 ms 1704 KB Output is correct
10 Correct 753 ms 1704 KB Output is correct
11 Correct 794 ms 1680 KB Output is correct
12 Correct 444 ms 1612 KB Output is correct
13 Correct 382 ms 1760 KB Output is correct
14 Correct 378 ms 1756 KB Output is correct
15 Correct 384 ms 1796 KB Output is correct
16 Correct 375 ms 1812 KB Output is correct
17 Correct 374 ms 1756 KB Output is correct
18 Correct 542 ms 1344 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1356 KB Output is correct
2 Correct 540 ms 1432 KB Output is correct
3 Correct 807 ms 1528 KB Output is correct
4 Correct 544 ms 1544 KB Output is correct
5 Correct 732 ms 1532 KB Output is correct
6 Correct 574 ms 1528 KB Output is correct
7 Correct 611 ms 1604 KB Output is correct
8 Correct 643 ms 1604 KB Output is correct
9 Correct 151 ms 1448 KB Output is correct
10 Correct 206 ms 1564 KB Output is correct
11 Correct 138 ms 1604 KB Output is correct
12 Correct 217 ms 1624 KB Output is correct
13 Correct 845 ms 1628 KB Output is correct
14 Correct 603 ms 1448 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 1552 KB Output is correct
2 Correct 416 ms 1548 KB Output is correct
3 Correct 718 ms 1564 KB Output is correct
4 Correct 422 ms 1476 KB Output is correct
5 Correct 69 ms 616 KB Output is correct
6 Correct 222 ms 1072 KB Output is correct
7 Correct 432 ms 1348 KB Output is correct
8 Correct 560 ms 1308 KB Output is correct
9 Correct 526 ms 1424 KB Output is correct
10 Correct 135 ms 800 KB Output is correct
11 Correct 343 ms 1340 KB Output is correct

Subtask #6
0 / 51.0

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