oj.uz

Submission #133786

# Submission time Handle Problem Language Result Execution time Memory
133786 2019-07-21T11:00:32 Z dvdg6566 Toy Train (IOI17_train) C++14
12 / 100
 12 ms 2936 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define pb emplace_back
#define mp make_pair
#define MAXN 5010
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
 
vi res;
vi U[MAXN],V[MAXN];
vi stat;
int vis[MAXN];
vi bad;
int outdeg[MAXN];
int A[MAXN];
int N;

queue<int> q;
int done[MAXN];
 
void dest(int x){
	done[x]=1;
	q.push(x);
	while(SZ(q)){
		int t = q.front();q.pop();
		res[t]=1;
		// cout<<"Remove "<<t<<'\n';
		for (auto i : U[t])if(!done[i]){
			if (A[i] == 1){
				// A owns it then can just remove
				q.push(i);
				done[i]=1;
			}else{
				--outdeg[i];
				if (outdeg[i] == 0){q.push(i);done[i]=1;}
			}
		}
	}
}
 
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	N = SZ(a);
	res.resize(N,0);
	for (int i=0;i<N;++i)A[i] = a[i];
	int m = SZ(u);
	for (int i=0;i<m;++i){
		V[u[i]].pb(v[i]);
		U[v[i]].pb(u[i]);
		// cout<<"Appending "<<u[i]<<" to "<<v[i]<<'\n';
		++outdeg[u[i]];
	}
	for (int i=0;i<N;++i)if(r[i])stat.pb(i);
	assert(SZ(stat) == 1);
	int rt = stat[0];
	dest(rt);
	// The node needs to be able to directly reach one of the done nodes
	if (A[rt]){
		for (auto v : V[rt])if(done[v])return res;
	}
	else{
		int ok = 1;
		for (auto v : V[rt])if (!done[v])ok = 0;
		if (ok)return res;
	}
	for (int  i=0;i<N;++i)res[i]=0;
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1500 KB Output is correct
2 Correct 12 ms 1400 KB Output is correct
3 Correct 12 ms 1528 KB Output is correct
4 Correct 11 ms 1404 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 8 ms 1300 KB Output is correct
8 Correct 8 ms 1400 KB Output is correct
9 Correct 8 ms 1272 KB Output is correct
10 Correct 4 ms 764 KB Output is correct
11 Correct 8 ms 1272 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -