oj.uz

Submission #641121

# Submission time Handle Problem Language Result Execution time Memory
641121 2022-09-16T03:36:32 Z ggoh Toy Train (IOI17_train) C++14
28 / 100
 486 ms 45924 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
 
int n,m,ch[5005],is[2],V[5005][5005];
vector<int>G[5005],T;
void f(vector<int> &a)
{
	while(1)
	{
		T.clear();
		for(int i=0;i<n;i++)
		{
			if(!ch[i])
			{
				is[0]=is[1]=0;
				for(auto &k:G[i])
				{
					if(ch[k])
					{
						V[i][k]=1;
						is[1]=1;
					}
					else is[0]=1;
				}
				if((a[i] && is[1]) || (!a[i] && !is[0]))T.push_back(i);
			}
		}
		if(!sz(T))break;
		for(auto &k:T)ch[k]=1;
	}
}
void g(vector<int> &a)
{
	while(1)
	{
		T.clear();
		for(int i=0;i<n;i++)
		{
			if(ch[i])
			{
				is[0]=is[1]=0;
				for(auto &k:G[i])
				{
					if(!ch[k])is[0]=1;
					else
					{
						if(V[i][i] || V[i][k])is[1]=1;
					}
				}
				if((a[i] && !is[1]) || (!a[i] && is[0]))T.push_back(i);
			}
		}
		if(!sz(T))break;
		for(auto &k:T)ch[k]=0;
	}
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n=sz(a);m=sz(u);
	vector<int> res(n);
	for(int i=0;i<m;i++)G[u[i]].push_back(v[i]);
	for(int i=0;i<n;i++)
	{
		ch[i]=r[i];
		if(ch[i])V[i][i]=1;
	}
	f(a);
	g(a);
	for(int i=0;i<n;i++)res[i]=ch[i];
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19284 KB Output is correct
2 Correct 14 ms 19540 KB Output is correct
3 Correct 12 ms 19632 KB Output is correct
4 Correct 13 ms 19504 KB Output is correct
5 Correct 20 ms 19156 KB Output is correct
6 Correct 19 ms 18608 KB Output is correct
7 Correct 11 ms 17720 KB Output is correct
8 Correct 19 ms 20052 KB Output is correct
9 Correct 10 ms 17236 KB Output is correct
10 Correct 10 ms 14924 KB Output is correct
11 Correct 6 ms 11060 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 21128 KB Output is correct
2 Correct 441 ms 21316 KB Output is correct
3 Correct 312 ms 21336 KB Output is correct
4 Incorrect 24 ms 29000 KB 3rd lines differ - on the 17th token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22740 KB Output is correct
2 Correct 28 ms 45644 KB Output is correct
3 Correct 19 ms 24148 KB Output is correct
4 Correct 19 ms 29396 KB Output is correct
5 Correct 88 ms 33100 KB Output is correct
6 Correct 140 ms 37208 KB Output is correct
7 Correct 77 ms 38828 KB Output is correct
8 Correct 20 ms 22432 KB Output is correct
9 Correct 16 ms 21844 KB Output is correct
10 Correct 18 ms 29140 KB Output is correct
11 Correct 17 ms 24492 KB Output is correct
12 Correct 26 ms 30036 KB Output is correct
13 Correct 27 ms 40820 KB Output is correct
14 Correct 29 ms 45924 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35412 KB Output is correct
2 Correct 23 ms 30936 KB Output is correct
3 Correct 25 ms 36524 KB Output is correct
4 Correct 28 ms 35216 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 6 ms 3412 KB Output is correct
8 Correct 8 ms 3412 KB Output is correct
9 Correct 6 ms 3540 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 8 ms 5588 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19284 KB Output is correct
2 Correct 14 ms 19540 KB Output is correct
3 Correct 12 ms 19632 KB Output is correct
4 Correct 13 ms 19504 KB Output is correct
5 Correct 20 ms 19156 KB Output is correct
6 Correct 19 ms 18608 KB Output is correct
7 Correct 11 ms 17720 KB Output is correct
8 Correct 19 ms 20052 KB Output is correct
9 Correct 10 ms 17236 KB Output is correct
10 Correct 10 ms 14924 KB Output is correct
11 Correct 6 ms 11060 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 1 ms 428 KB Output is correct
17 Correct 0 ms 468 KB Output is correct
18 Incorrect 1 ms 468 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
19 Halted 0 ms 0 KB -