oj.uz

답안 #409501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409501 2021-05-21T00:35:26 Z rqi 장난감 기차 (IOI17_train) C++14
11 / 100
 896 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];

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

queue<int> to_unForce;

void iForce(int node){
	for(auto u: radj[node]){
		if(forced[u]) continue;
		if(a[u] == 1){
			cur_deg[u]++;
			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++){
		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);
	for(auto u: radj[node]){
		if(forced[u]){
			cur_deg[u]--;
			if(cur_deg[u] == 0){
				forced[u] = 0;
				to_unForce.push(u);

				if(!bad[u] && a[u] == 1){ //second condition unnecessary
					bad[u] = 1;
					q.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]);
	}

	initForce();

	

	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++){
		bad_cur_deg[i] = sz(adj[i]);
		if(dp[i] == 1){
			q.push(i);
			bad[i] = 1;
			//cout << "initial bad: " << 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);
			}
		}
		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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 200 ms 1348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 460 KB Output is correct
2 Correct 41 ms 560 KB Output is correct
3 Correct 41 ms 460 KB Output is correct
4 Incorrect 41 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 368 ms 1840 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 1560 KB Output is correct
2 Correct 525 ms 1672 KB Output is correct
3 Correct 813 ms 1860 KB Output is correct
4 Correct 511 ms 1776 KB Output is correct
5 Correct 718 ms 1776 KB Output is correct
6 Correct 551 ms 1752 KB Output is correct
7 Correct 581 ms 1740 KB Output is correct
8 Correct 626 ms 1712 KB Output is correct
9 Correct 126 ms 1612 KB Output is correct
10 Correct 201 ms 1812 KB Output is correct
11 Correct 135 ms 1812 KB Output is correct
12 Correct 211 ms 1800 KB Output is correct
13 Correct 848 ms 1784 KB Output is correct
14 Correct 598 ms 1676 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 896 ms 1788 KB 3rd lines differ - on the 60th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 200 ms 1348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -