oj.uz

Submission #243201

# Submission time Handle Problem Language Result Execution time Memory
243201 2020-06-30T14:27:28 Z crossing0ver Toy Train (IOI17_train) C++17
27 / 100
 1452 ms 1912 KB 
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
//#include "train.h"
using namespace std;
int n,m;
vi X,Y,good,who,adj[5009];
 
vi CASE1() {
	vi ans(n);
	for (int i = n-1; i >= 0; i--) {
		bool flag = 0;
		for (int j : adj[i]) {
			if (j == i && who[i] == good[i]) {
				ans[i] = who[i];
				flag = 1;
				break;
			}
			if (who[i] == ans[j] && j != i) {
				flag = 1;
				ans[i] = ans[j];
				break;
			}
		}
		if (flag == 0) ans[i] = (!who[i]);
	}
	return ans;
}
vector<int> vis(5005),P(5005),G(5005),depth(5005);
bool dfs(int v,int tp,int root) {
	vis[v] = 1;
	bool ans = 0;
	if (tp && good[v] == 2) ans = 1;
	for (int i : adj[v]) {
		if (vis[i]) {
          if (root == i && !tp)
          good[i] = 2;
        }
		else ans|=dfs(i,tp,root);
	}
	return ans;
}
vi CASE2() {
	vi ans(n);//,vis(n),P(n),G(n),depth(n);
	for (int i = 0; i < n; i++) {
		if (good[i]) dfs(i,0,i);
		fill(vis.begin(),vis.end(),0);
	}
	for (int i = 0; i < n; i++) {
		ans[i] = dfs(i,1,0);
		fill(vis.begin(),vis.end(),0);
	}
	return ans;
}
bool dfs1(int root,int v,int tp) {
	vis[v] = 1;
	bool ans = 0;
	if (tp == 1 && good[v] == -1) ans = 1;
	for (int i : adj[v]) {
		if (good[i] == 1 && tp == 0) continue;
		if (!vis[i]) ans|=dfs1(root,i,tp);
		else {
			if (tp == 0)
			if (root == i) good[root] = -1;
		}
	}
	return ans;
}
vi CASE3() {
	vi ans(n);
	for (int i = 0; i < n; i++) {
		if(!good[i]) dfs1(i,i,0); 
		fill(vis.begin(),vis.end(),0);
	}
	for (int i = 0; i < n ; i++) {
		ans[i] = !dfs1(0,i,1);
		fill(vis.begin(),vis.end(),0);
	}
	return ans;
}
vi who_wins(vi a1, vi r, vi st, vi en) {
	n = a1.size(), m = st.size();
	X = st; Y = en;
	for (int i = 0; i < m; i++)
		adj[X[i]].pb(Y[i]);
	good = r;
	who = a1;
	bool case1 = 1,case2 = 1,case3 = 1;
	for (int i = 0; i < m; i++) {
		if (X[i] != Y[i] && X[i]+1 != Y[i])
			case1 = 0;
	}
	for (int i = 0;i < n; i++)
		if (who[i] == 0) case2 = 0;
		else case3 = 0;
		
	if (case1) return CASE1();	
	if (case2) return CASE2();
	if (case3) return CASE3();
//	return res;
	return vector<int>();
}
/*
main() {
	cin >> n >> m;
	vi r(n),a1(n),st(m),en(m);
	for (int i = 0; i < n; i++) 
		cin >> a1[i];
	for (int i = 0; i < n ;i++)
		cin >> r[i];
	for (int i = 0; i < m ;i++) {
		int x,y;
		cin >> st[i] >> en[i];
	}
	vi ans = who_wins(a1,r,st,en);
	for (int i :ans) cout << i <<' ';
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1024 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 8 ms 896 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 1536 KB Output is correct
2 Correct 193 ms 1656 KB Output is correct
3 Correct 203 ms 1524 KB Output is correct
4 Correct 1301 ms 1528 KB Output is correct
5 Correct 815 ms 1528 KB Output is correct
6 Correct 623 ms 1528 KB Output is correct
7 Correct 668 ms 1400 KB Output is correct
8 Correct 299 ms 1280 KB Output is correct
9 Correct 302 ms 1528 KB Output is correct
10 Correct 379 ms 1280 KB Output is correct
11 Correct 328 ms 1280 KB Output is correct
12 Correct 51 ms 1280 KB Output is correct
13 Correct 1062 ms 1532 KB Output is correct
14 Correct 1039 ms 1408 KB Output is correct
15 Correct 1065 ms 1528 KB Output is correct
16 Correct 1050 ms 1528 KB Output is correct
17 Correct 1059 ms 1524 KB Output is correct
18 Correct 449 ms 1152 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 1528 KB Output is correct
2 Correct 280 ms 1528 KB Output is correct
3 Correct 622 ms 1604 KB Output is correct
4 Correct 710 ms 1536 KB Output is correct
5 Correct 731 ms 1536 KB Output is correct
6 Correct 614 ms 1536 KB Output is correct
7 Correct 672 ms 1684 KB Output is correct
8 Correct 549 ms 1528 KB Output is correct
9 Correct 55 ms 1408 KB Output is correct
10 Correct 1445 ms 1788 KB Output is correct
11 Correct 1226 ms 1912 KB Output is correct
12 Correct 1452 ms 1784 KB Output is correct
13 Correct 1113 ms 1784 KB Output is correct
14 Correct 653 ms 1656 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1280 KB WA in grader: Wrong returned array size
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1024 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 8 ms 896 KB Output is correct
12 Incorrect 4 ms 512 KB WA in grader: Wrong returned array size
13 Halted 0 ms 0 KB -