oj.uz

Submission #409511

# Submission time Handle Problem Language Result Execution time Memory
409511 2021-05-21T02:22:35 Z rqi Toy Train (IOI17_train) C++14
11 / 100
 878 ms 1860 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]) 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(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 211 ms 1228 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 Correct 42 ms 544 KB Output is correct
2 Correct 42 ms 532 KB Output is correct
3 Correct 41 ms 460 KB Output is correct
4 Incorrect 42 ms 460 KB 3rd lines differ - on the 4th token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 1796 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 517 ms 1612 KB Output is correct
3 Correct 793 ms 1860 KB Output is correct
4 Correct 532 ms 1756 KB Output is correct
5 Correct 728 ms 1740 KB Output is correct
6 Correct 549 ms 1740 KB Output is correct
7 Correct 582 ms 1716 KB Output is correct
8 Correct 649 ms 1692 KB Output is correct
9 Correct 156 ms 1760 KB Output is correct
10 Correct 200 ms 1764 KB Output is correct
11 Correct 135 ms 1740 KB Output is correct
12 Correct 210 ms 1740 KB Output is correct
13 Correct 802 ms 1740 KB Output is correct
14 Correct 583 ms 1640 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 1764 KB Output is correct
2 Correct 397 ms 1752 KB Output is correct
3 Correct 714 ms 1752 KB Output is correct
4 Correct 405 ms 1648 KB Output is correct
5 Correct 62 ms 588 KB Output is correct
6 Correct 210 ms 1164 KB Output is correct
7 Correct 408 ms 1380 KB Output is correct
8 Incorrect 548 ms 1440 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 Incorrect 211 ms 1228 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -