oj.uz

Submission #434623

# Submission time Handle Problem Language Result Execution time Memory
434623 2021-06-21T13:18:00 Z frodakcin Comparing Plants (IOI20_plants) C++11
25 / 100
 2667 ms 119916 KB 
#include "plants.h"
#include <queue>
#include <bitset>

const int MN = 5e3+10;
const int INF = 0x3f3f3f3f;

int N, K, ts[MN], ctr;
bool v[MN];
std::vector<int> a[MN]; // i > a[i][...] -- dag
std::bitset<MN> vis[MN];

void dfs(int n)
{
	v[n]=1;
	for(int x:a[n])
		if(!v[x])
			dfs(x);
	ts[ctr++]=n;
}

void init(int k, std::vector<int> r) {
	K=k, N=r.size();
	
	std::queue<int> q;
	int zc=0;
	for(int i=N-K;i<N;++i)
		zc += !r[i];
	for(int i=0;i<N;++i)
	{
		zc -= !r[(N-K+i)%N];
		if(zc==0 && r[i]==0)
			q.push(i);
		zc += !r[i];
	}

	for(;!q.empty();)
	{
		int n=q.front(); q.pop();
		if(r[n] < 0) continue;
		
		// check
		bool ok=1;
		for(int i=1;i<K;++i)
			if(r[(n-i+N)%N]==0)
				ok=0;
		if(!ok) continue;

		// add
		r[n]=-1;
		for(int i=K-1;i>0;--i)
			--r[(n-i+N)%N];
		for(int i=1;i<K;++i)
			if(r[(n+i)%N] == 0)
			{
				q.push((n+i)%N);
				break;
			}
		for(int i=K-1;i>0;--i)
			if(r[(n-i+N)%N] == 0)
			{
				q.push((n-i+N)%N);
				break;
			}
		for(int i=1;i<K;++i)
			if(r[(n+i)%N] >= 0)
				a[n].push_back((n+i)%N);
		for(int i=1;i<K;++i)
			if(r[(n-i+N)%N] >= 0)
				a[n].push_back((n-i+N)%N);
	}

	for(int i=0;i<N;++i)
		if(!v[i])
			dfs(i);

	for(int i=0;i<N;++i)
		vis[i].set(i);
	for(int i=0;i<N;++i)
		for(int x:a[ts[i]])
			vis[ts[i]]|=vis[x];
	return;
}

int compare_plants(int x, int y)
{
	if(vis[x][y]) return 1;
	if(vis[y][x]) return -1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 59 ms 3156 KB Output is correct
7 Runtime error 52 ms 5652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 85 ms 5732 KB Output is correct
7 Correct 2175 ms 99704 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 84 ms 5732 KB Output is correct
10 Correct 2185 ms 99652 KB Output is correct
11 Correct 1276 ms 68508 KB Output is correct
12 Correct 1426 ms 68416 KB Output is correct
13 Correct 2667 ms 119916 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 85 ms 5732 KB Output is correct
7 Correct 2175 ms 99704 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 84 ms 5732 KB Output is correct
10 Correct 2185 ms 99652 KB Output is correct
11 Correct 1276 ms 68508 KB Output is correct
12 Correct 1426 ms 68416 KB Output is correct
13 Correct 2667 ms 119916 KB Output is correct
14 Runtime error 54 ms 6208 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 70 ms 4684 KB Output is correct
4 Runtime error 81 ms 8772 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 15 ms 1228 KB Output is correct
8 Correct 19 ms 1376 KB Output is correct
9 Correct 17 ms 1208 KB Output is correct
10 Correct 18 ms 1332 KB Output is correct
11 Correct 15 ms 1228 KB Output is correct
12 Correct 16 ms 1200 KB Output is correct
13 Correct 23 ms 1700 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 12 ms 1612 KB Output is correct
6 Runtime error 68 ms 8592 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 59 ms 3156 KB Output is correct
7 Runtime error 52 ms 5652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -