oj.uz

Submission #434493

# Submission time Handle Problem Language Result Execution time Memory
434493 2021-06-21T11:11:56 Z frodakcin Comparing Plants (IOI20_plants) C++11
14 / 100
 1074 ms 84108 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] > INF/2) 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]=INF;
		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);
				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);
				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 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 Incorrect 1 ms 332 KB Output isn't correct
5 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 22 ms 1216 KB Output is correct
7 Correct 542 ms 8408 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 22 ms 1168 KB Output is correct
10 Correct 549 ms 8340 KB Output is correct
11 Correct 1074 ms 84108 KB Output is correct
12 Correct 379 ms 8300 KB Output is correct
13 Correct 658 ms 8280 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 22 ms 1216 KB Output is correct
7 Correct 542 ms 8408 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 22 ms 1168 KB Output is correct
10 Correct 549 ms 8340 KB Output is correct
11 Correct 1074 ms 84108 KB Output is correct
12 Correct 379 ms 8300 KB Output is correct
13 Correct 658 ms 8280 KB Output is correct
14 Runtime error 63 ms 7320 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 0 ms 332 KB Output is correct
3 Incorrect 67 ms 4512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 4 ms 972 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -