oj.uz

Submission #434500

# Submission time Handle Problem Language Result Execution time Memory
434500 2021-06-21T11:15:28 Z frodakcin Comparing Plants (IOI20_plants) C++11
25 / 100
 2542 ms 119408 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)
			{
				a[n].push_back((n+i)%N);
				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)
			{
				a[n].push_back((n-i+N)%N);
				if(r[(n-i+N)%N] == 0) q.push((n-i+N)%N);
				//break;
			}
	}

	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 0 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 0 ms 332 KB Output is correct
6 Correct 59 ms 3156 KB Output is correct
7 Runtime error 51 ms 5656 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 0 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 2 ms 460 KB Output is correct
6 Correct 97 ms 5676 KB Output is correct
7 Correct 2069 ms 99132 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 82 ms 5668 KB Output is correct
10 Correct 2082 ms 99168 KB Output is correct
11 Correct 1292 ms 92572 KB Output is correct
12 Correct 1297 ms 67888 KB Output is correct
13 Correct 2542 ms 119408 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 0 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 2 ms 460 KB Output is correct
6 Correct 97 ms 5676 KB Output is correct
7 Correct 2069 ms 99132 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 82 ms 5668 KB Output is correct
10 Correct 2082 ms 99168 KB Output is correct
11 Correct 1292 ms 92572 KB Output is correct
12 Correct 1297 ms 67888 KB Output is correct
13 Correct 2542 ms 119408 KB Output is correct
14 Runtime error 49 ms 5664 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 66 ms 4576 KB Output is correct
4 Runtime error 75 ms 10180 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 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 14 ms 1484 KB Output is correct
8 Correct 18 ms 1740 KB Output is correct
9 Correct 15 ms 1484 KB Output is correct
10 Correct 23 ms 1628 KB Output is correct
11 Correct 15 ms 1524 KB Output is correct
12 Correct 15 ms 1612 KB Output is correct
13 Correct 23 ms 1996 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 0 ms 332 KB Output is correct
5 Correct 14 ms 1632 KB Output is correct
6 Runtime error 71 ms 10888 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 0 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 0 ms 332 KB Output is correct
6 Correct 59 ms 3156 KB Output is correct
7 Runtime error 51 ms 5656 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -