oj.uz

Submission #886032

# Submission time Handle Problem Language Result Execution time Memory
886032 2023-12-11T12:02:53 Z waldi Toy Train (IOI17_train) C++17
27 / 100
 1782 ms 1616 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){
			ret[start] = 1;
			
			vector<bool> odw(n, 0);
			function<void(int)> dfs = [&](int w){
				odw[w] = 1;
				if(czy_cykl[w]) ret[start] = 0;
				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 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 780 KB Output is correct
7 Correct 2 ms 868 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 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 289 ms 1472 KB Output is correct
2 Correct 288 ms 1372 KB Output is correct
3 Correct 285 ms 1372 KB Output is correct
4 Correct 1770 ms 1348 KB Output is correct
5 Correct 1355 ms 1300 KB Output is correct
6 Correct 909 ms 1204 KB Output is correct
7 Correct 809 ms 1172 KB Output is correct
8 Correct 471 ms 1112 KB Output is correct
9 Correct 369 ms 1196 KB Output is correct
10 Correct 585 ms 1148 KB Output is correct
11 Correct 499 ms 1112 KB Output is correct
12 Correct 37 ms 1116 KB Output is correct
13 Correct 1729 ms 1380 KB Output is correct
14 Correct 1782 ms 1372 KB Output is correct
15 Correct 1779 ms 1372 KB Output is correct
16 Correct 1776 ms 1376 KB Output is correct
17 Correct 1689 ms 1372 KB Output is correct
18 Correct 437 ms 1364 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 1116 KB Output is correct
2 Correct 217 ms 1276 KB Output is correct
3 Correct 381 ms 1396 KB Output is correct
4 Correct 417 ms 1384 KB Output is correct
5 Correct 532 ms 1392 KB Output is correct
6 Correct 443 ms 1380 KB Output is correct
7 Correct 476 ms 1616 KB Output is correct
8 Correct 328 ms 1328 KB Output is correct
9 Correct 22 ms 1112 KB Output is correct
10 Correct 855 ms 1588 KB Output is correct
11 Correct 856 ms 1576 KB Output is correct
12 Correct 876 ms 1576 KB Output is correct
13 Correct 881 ms 1616 KB Output is correct
14 Correct 503 ms 1348 KB Output is correct

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 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 780 KB Output is correct
7 Correct 2 ms 868 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Incorrect 0 ms 600 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -