oj.uz

Submission #886028

# Submission time Handle Problem Language Result Execution time Memory
886028 2023-12-11T11:58:47 Z waldi Toy Train (IOI17_train) C++17
16 / 100
 1810 ms 1624 KB 
#include "train.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
	int n = ssize(a);
	int m = ssize(u);
	vector<int> ret(n);
	
	vector<vector<int>> g(n);
	REP(i, m) g[u[i]].emplace_back(v[i]);
	
	bool sciezka = 1;
	REP(i, m) if(u[i] != v[i] && v[i] != u[i]+1) sciezka = 0;
	if(sciezka){
		for(int i = n; ~--i;){
			bool petla = 0, dalej = 0;
			for(int j : g[i]){
				if(j == i) petla = 1;
				if(j == i+1) dalej = 1;
			}
			
			if(a[i]){
				ret[i] = 0;
				if(petla && r[i]) ret[i] |= 1;
				if(dalej) ret[i] |= ret[i+1];
			}
			else{
				ret[i] = 1;
				if(petla && !r[i]) ret[i] &= 0;
				if(dalej) ret[i] &= ret[i+1];
			}
		}
		return ret;
	}
	
	bool wszystkie_a = 1;
	REP(i, n) if(!a[i]) wszystkie_a = 0;
	if(wszystkie_a){
		vector<int> czy_cykl(n, 0);
		REP(start, n){
			vector<bool> odw(n, 0);
			function<void(int)> dfs = [&](int w){
				odw[w] = 1;
				for(int i : g[w]){
					if(i == start) czy_cykl[start] = 1;
					if(!odw[i]) dfs(i);
				}
			};
			dfs(start);
		}
		
		REP(start, n){
			vector<bool> odw(n, 0);
			function<void(int)> dfs = [&](int w){
				odw[w] = 1;
				if(r[w] && czy_cykl[w]) ret[start] = 1;
				for(int i : g[w]) if(!odw[i]) dfs(i);
			};
			dfs(start);
		}
		
		return ret;
	}
	
	bool wszystkie_b = 1;
	REP(i, n) if(a[i]) wszystkie_b = 0;
	if(wszystkie_b){
		vector<int> czy_cykl(n, 0);
		REP(start, n) if(!r[start]){
			vector<bool> odw(n, 0);
			function<void(int)> dfs = [&](int w){
				odw[w] = 1;
				for(int i : g[w]) if(!r[i]){
					if(i == start) czy_cykl[start] = 1;
					if(!odw[i]) dfs(i);
				}
			};
			dfs(start);
		}
		
		REP(start, n){
			vector<bool> odw(n, 0);
			function<void(int)> dfs = [&](int w){
				odw[w] = 1;
				if(czy_cykl[w]) ret[start] = 1;
				for(int i : g[w]) if(!odw[i]) dfs(i);
			};
			dfs(start);
		}
		
		return ret;
	}
	
	REP(i, n){
		
	}
	return ret;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 1472 KB Output is correct
2 Correct 277 ms 1372 KB Output is correct
3 Correct 280 ms 1396 KB Output is correct
4 Correct 1739 ms 1364 KB Output is correct
5 Correct 1283 ms 1296 KB Output is correct
6 Correct 886 ms 1212 KB Output is correct
7 Correct 789 ms 1176 KB Output is correct
8 Correct 443 ms 1188 KB Output is correct
9 Correct 396 ms 1200 KB Output is correct
10 Correct 587 ms 1144 KB Output is correct
11 Correct 502 ms 1160 KB Output is correct
12 Correct 44 ms 1116 KB Output is correct
13 Correct 1810 ms 1392 KB Output is correct
14 Correct 1730 ms 1372 KB Output is correct
15 Correct 1736 ms 1620 KB Output is correct
16 Correct 1714 ms 1624 KB Output is correct
17 Correct 1709 ms 1372 KB Output is correct
18 Correct 414 ms 1184 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 667 ms 1112 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 5 ms 1116 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 3 ms 860 KB Output is correct
2 Correct 3 ms 776 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 856 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 884 KB Output is correct
12 Incorrect 0 ms 344 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -