oj.uz

Submission #296237

# Submission time Handle Problem Language Result Execution time Memory
296237 2020-09-10T12:29:26 Z b00n0rp Toy Train (IOI17_train) C++17
0 / 100
 13 ms 1920 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)

const int MAXN = 5005;

int n,m;
int indeg[MAXN];
vi adj[MAXN],rev[MAXN];
vi ans;

vi charging,own;

vi f(vi tot,vi sub,int type){
	for(auto x:tot){
		indeg[x] = rev[x].size();
		if(own[x] == type) indeg[x] = 1;
	}
	queue<int> q;
	for(auto x:sub){
		indeg[x] = 0;
		q.push(x);
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto v:rev[u]){
			indeg[v]--;
			if(!indeg[v]){
				sub.pb(v);
				q.push(v);
			}
		}
	}
	return sub;
}

void solve(vi gg){
	// cout << gg.size() << endl;
	// for(auto x:gg) cout << x << " "; cout << endl;
	if(gg.empty()) return;

	vi ch,win,lose,nwin,nlose;
	for(auto x:gg){
		if(charging[x]) ch.pb(x);
	}
	win = f(gg,ch,1);
	if(win.size() == gg.size()){
		for(auto x:gg) ans[x] = 1;
		return;
	}
	bitset<MAXN> w;
	for(auto x:win) w[x] = 1;
	for(auto x:gg){
		if(!w[x]) nwin.pb(x);
	}
	lose = f(gg,nwin,0);
	w.reset();
	for(auto x:lose){
		w[x] = 1;
		ans[x] = 0;
	}
	for(auto x:gg){
		if(!w[x]) nlose.pb(x);
	}
	solve(nlose);
}

vi who_wins(vi a, vi r, vi u, vi v){
	charging = r;
	own = a;
	n = a.size();
	m = u.size();
	REP(i,m){
		adj[u[i]].pb(v[i]);
		rev[v[i]].pb(u[i]);
	}
	ans.resize(n);
	vi gg;
	REP(i,n) gg.pb(i);
	solve(gg);
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1536 KB Output is correct
2 Incorrect 8 ms 1664 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1920 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1664 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1792 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1536 KB Output is correct
2 Incorrect 8 ms 1664 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -