oj.uz

Submission #415293

# Submission time Handle Problem Language Result Execution time Memory
415293 2021-05-31T20:08:49 Z CSQ31 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 54724 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);
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
		else nxt[i][0] = to+n;
		
		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
		else nxt[i+n][0] = to+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];
		}
		
	}	
  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);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9932 KB Output is correct
2 Correct 9 ms 9932 KB Output is correct
3 Correct 8 ms 9932 KB Output is correct
4 Correct 7 ms 9648 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 10040 KB Output is correct
7 Correct 9 ms 9708 KB Output is correct
8 Correct 9 ms 9932 KB Output is correct
9 Correct 9 ms 10316 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9932 KB Output is correct
2 Correct 9 ms 9932 KB Output is correct
3 Correct 8 ms 9932 KB Output is correct
4 Correct 7 ms 9648 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 10040 KB Output is correct
7 Correct 9 ms 9708 KB Output is correct
8 Correct 9 ms 9932 KB Output is correct
9 Correct 9 ms 10316 KB Output is correct
10 Correct 6 ms 9704 KB Output is correct
11 Correct 28 ms 16364 KB Output is correct
12 Correct 54 ms 21632 KB Output is correct
13 Correct 150 ms 34864 KB Output is correct
14 Correct 251 ms 50472 KB Output is correct
15 Correct 192 ms 51072 KB Output is correct
16 Correct 197 ms 39240 KB Output is correct
17 Correct 162 ms 35436 KB Output is correct
18 Correct 75 ms 21520 KB Output is correct
19 Correct 225 ms 50424 KB Output is correct
20 Correct 245 ms 51084 KB Output is correct
21 Correct 185 ms 38992 KB Output is correct
22 Correct 164 ms 35132 KB Output is correct
23 Correct 246 ms 54724 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9932 KB Output is correct
2 Correct 9 ms 9932 KB Output is correct
3 Correct 8 ms 9932 KB Output is correct
4 Correct 7 ms 9648 KB Output is correct
5 Correct 8 ms 9676 KB Output is correct
6 Correct 7 ms 10040 KB Output is correct
7 Correct 9 ms 9708 KB Output is correct
8 Correct 9 ms 9932 KB Output is correct
9 Correct 9 ms 10316 KB Output is correct
10 Correct 6 ms 9704 KB Output is correct
11 Correct 28 ms 16364 KB Output is correct
12 Correct 54 ms 21632 KB Output is correct
13 Correct 150 ms 34864 KB Output is correct
14 Correct 251 ms 50472 KB Output is correct
15 Correct 192 ms 51072 KB Output is correct
16 Correct 197 ms 39240 KB Output is correct
17 Correct 162 ms 35436 KB Output is correct
18 Correct 75 ms 21520 KB Output is correct
19 Correct 225 ms 50424 KB Output is correct
20 Correct 245 ms 51084 KB Output is correct
21 Correct 185 ms 38992 KB Output is correct
22 Correct 164 ms 35132 KB Output is correct
23 Correct 246 ms 54724 KB Output is correct
24 Correct 18 ms 9720 KB Output is correct
25 Correct 4854 ms 16424 KB Output is correct
26 Execution timed out 5062 ms 21660 KB Time limit exceeded
27 Halted 0 ms 0 KB -