oj.uz

Submission #415301

# Submission time Handle Problem Language Result Execution time Memory
415301 2021-05-31T20:47:33 Z CSQ31 Tropical Garden (IOI11_garden) C++14
69 / 100
 338 ms 67784 KB 
#include "garden.h"
#include <bits/stdc++.h>
#include "gardenlib.h"
using namespace std;
#define sz(a) (int)(a.size())
#define pb push_back
#define se second
typedef vector<vector<int>> vii;
typedef pair<int,int> pii;
const int MAXN = 4e5+5;
int nxt[MAXN][31];
vector<vector<pii>> g1(MAXN);
vii g2(MAXN);
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
	for(int i=0;i<m;i++){
		g1[r[i][0]].pb({i,r[i][1]});
		g1[r[i][1]].pb({i,r[i][0]});
	}
	for(int i=0;i<n;i++)sort(g1[i].begin(),g1[i].end());
	for(int i=0;i<n;i++){
		int to = g1[i][0].se;
		if(g1[to][0].se != i){
			nxt[i][0] = to; //not beautiful
			g2[to].pb(i);
		}
		else {
			nxt[i][0] = to+n;
			g2[to+n].pb(i);
		}
		
		to = (sz(g1[i]) > 1)?g1[i][1].se:g1[i][0].se;
		if(g1[to][0].se != i){
			nxt[i+n][0] = to; //not beautiful
			g2[to].pb(i+n);
		}
		else {
			nxt[i+n][0] = to+n;
			g2[to+n].pb(i+n);
		}
	}
	for(int k=1;k<31;k++){
		for(int i=0;i<2*n;i++){
			nxt[i][k] = nxt[nxt[i][k-1]][k-1];
		}
		
	}	
	if(q == 1){
	  for(int i=0; i<q; i++) { 
		  int ans = 0;
		  for(int x=0;x<n;x++){
			  int cur = x;
			  int cnt = g[i];
			  for(int j=30;j>=0;j--){
				  if(cnt >= (1<<j)){
					  cur = nxt[cur][j];
					  cnt-=(1<<j);
				  }
			  }
			  if(cur == p || cur == p+n)ans++;
			  
		  } 
		  answer(ans);
	  }
	  return ;
	}
	vector<bool>cycle(2*n),vis(2*n);
	int i = 0;
	while(!vis[i]){
		vis[i] = 1;
		i = nxt[i][0];
	}
	int len = 0;
	while(!cycle[i]){
		cycle[i] = 1;
		len++;
		i = nxt[i][0];
	}
	vii d(2,vector<int>(2*n,2e9));
	queue<int>qq;
	qq.push(p);
	d[0][p] = 0;
	vis.assign(2*n,0);
	vis[p] = 1;
	while(!qq.empty()){
		int v = qq.front();
		qq.pop();
		for(int x:g2[v]){
			if(vis[x])continue;
			vis[x] =1;
			d[0][x] = d[0][v]+1;
			qq.push(x);
		}
	}
	d[1][p+n] = 0;
	qq.push(p+n);
	vis.assign(2*n,0);
	vis[p+n] = 1;
	while(!qq.empty()){
		int v = qq.front();
		qq.pop();
		for(int x:g2[v]){
			if(vis[x])continue;
			vis[x] =1;
			d[1][x] = d[1][v]+1;
			qq.push(x);
		}
	}
	for(int i=0;i<q;i++){
		int ans = 0;
		for(int j=0;j<n;j++){
			if((g[i] >= d[0][j] && (g[i]-d[0][j])%len == 0) || (g[i] >= d[1][j] && (g[i]-d[1][j])%len == 0))ans++;
		}
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19400 KB Output is correct
2 Correct 16 ms 19364 KB Output is correct
3 Correct 15 ms 19404 KB Output is correct
4 Correct 13 ms 19104 KB Output is correct
5 Correct 18 ms 19020 KB Output is correct
6 Correct 20 ms 19420 KB Output is correct
7 Correct 16 ms 19100 KB Output is correct
8 Correct 14 ms 19404 KB Output is correct
9 Correct 17 ms 19628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19400 KB Output is correct
2 Correct 16 ms 19364 KB Output is correct
3 Correct 15 ms 19404 KB Output is correct
4 Correct 13 ms 19104 KB Output is correct
5 Correct 18 ms 19020 KB Output is correct
6 Correct 20 ms 19420 KB Output is correct
7 Correct 16 ms 19100 KB Output is correct
8 Correct 14 ms 19404 KB Output is correct
9 Correct 17 ms 19628 KB Output is correct
10 Correct 13 ms 19148 KB Output is correct
11 Correct 42 ms 26664 KB Output is correct
12 Correct 118 ms 32164 KB Output is correct
13 Correct 140 ms 48888 KB Output is correct
14 Correct 264 ms 63204 KB Output is correct
15 Correct 271 ms 63836 KB Output is correct
16 Correct 330 ms 50404 KB Output is correct
17 Correct 220 ms 46184 KB Output is correct
18 Correct 70 ms 32076 KB Output is correct
19 Correct 278 ms 63096 KB Output is correct
20 Correct 338 ms 63840 KB Output is correct
21 Correct 284 ms 50496 KB Output is correct
22 Correct 213 ms 46016 KB Output is correct
23 Correct 298 ms 67784 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19400 KB Output is correct
2 Correct 16 ms 19364 KB Output is correct
3 Correct 15 ms 19404 KB Output is correct
4 Correct 13 ms 19104 KB Output is correct
5 Correct 18 ms 19020 KB Output is correct
6 Correct 20 ms 19420 KB Output is correct
7 Correct 16 ms 19100 KB Output is correct
8 Correct 14 ms 19404 KB Output is correct
9 Correct 17 ms 19628 KB Output is correct
10 Correct 13 ms 19148 KB Output is correct
11 Correct 42 ms 26664 KB Output is correct
12 Correct 118 ms 32164 KB Output is correct
13 Correct 140 ms 48888 KB Output is correct
14 Correct 264 ms 63204 KB Output is correct
15 Correct 271 ms 63836 KB Output is correct
16 Correct 330 ms 50404 KB Output is correct
17 Correct 220 ms 46184 KB Output is correct
18 Correct 70 ms 32076 KB Output is correct
19 Correct 278 ms 63096 KB Output is correct
20 Correct 338 ms 63840 KB Output is correct
21 Correct 284 ms 50496 KB Output is correct
22 Correct 213 ms 46016 KB Output is correct
23 Correct 298 ms 67784 KB Output is correct
24 Incorrect 14 ms 19148 KB Output isn't correct
25 Halted 0 ms 0 KB -