oj.uz

Submission #851275

# Submission time Handle Problem Language Result Execution time Memory
851275 2023-09-19T09:25:37 Z Halym2007 Tropical Garden (IOI11_garden) C++11
69 / 100
 5000 ms 83272 KB 
#include <bits/stdc++.h>
using namespace std;
const int LOG = 30;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define MAXM 150005
#define sz size()
#include "garden.h"
#include "gardenlib.h"

pair <int, int> dp1[MAXM][LOG], dp2[MAXM][LOG];
vector <int> adj[MAXM];

//void answer(int x) {
//	cout << x << " ";
//}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	for (int i = 0; i < M; ++i) {
		int u = R[i][0], v = R[i][1];
		adj[u].pb (v);
		adj[v].pb (u);
	}
	for (int i = 0; i < N; ++i) {
		if ((int)adj[i].sz) {
			dp1[i][0].ff = adj[i][0];
			dp1[i][0].ss = i;
			if ((int)adj[i].sz > 1) {
				dp2[i][0].ff = adj[i][1];
				dp2[i][0].ss = i;
			}
			else dp2[i][0] = dp1[i][0];
		}
	}
	
	for (int j = 1; j < LOG; ++j) {
		for (int i = 0; i < N; ++i) {
			int x = dp1[i][j - 1].ff;
			int y = dp1[i][j - 1].ss;
			if (adj[x][0] == y) {
				dp1[i][j] = dp2[x][j - 1];
			}
			else {
				dp1[i][j] = dp1[x][j - 1];
			}
			
			x = dp2[i][j - 1].ff;
			y = dp2[i][j - 1].ss;
			if (adj[x][0] == y) {
				dp2[i][j] = dp2[x][j - 1];
			}
			else {
				dp2[i][j] = dp1[x][j - 1];
			}
		}
	}
	for (int ii = 0; ii < Q; ++ii) {
		int val = G[ii];
		int jogap = 0;
		for (int i = 0; i < N; ++i) {
			int hp = i;
			int pr = -1;
			for (int j = LOG - 1; j >= 0; j--) {
				if (val>>j&1) {
					if (adj[hp][0] == pr) {
						auto tr = dp2[hp][j];
						hp = tr.ff;
						pr = tr.ss;
					}
					else {
						auto tr = dp1[hp][j];
						hp = tr.ff;
						pr = tr.ss;
					}
				} 
			}	
			if (hp == P) { 
				jogap++;
			}
		}
		answer (jogap);
	}
}




//
//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_M  1000000
//#define MAX_Q  2000
//
//static int N, M, P, Q;
//static int R[MAX_M][2];
//static int G[MAX_Q];
//
//void read_input()
//{
//  int i;
//  scanf("%d %d %d",&N,&M,&P);
//  for(i=0; i<M; i++)
//    scanf("%d %d",&R[i][0],&R[i][1]);
//  scanf("%d",&Q);
//  for(i=0; i<Q; i++)
//    scanf("%d",&G[i]);
//}
//
//
//
//int main() {
//	freopen("input.txt", "r", stdin);
//  read_input();
//  count_routes(N,M,P,R,Q,G);
//  return 0;
//}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 11096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 11096 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 14 ms 23896 KB Output is correct
12 Correct 28 ms 31064 KB Output is correct
13 Correct 115 ms 55376 KB Output is correct
14 Correct 150 ms 82512 KB Output is correct
15 Correct 138 ms 82516 KB Output is correct
16 Correct 93 ms 60752 KB Output is correct
17 Correct 108 ms 52596 KB Output is correct
18 Correct 32 ms 31228 KB Output is correct
19 Correct 152 ms 82596 KB Output is correct
20 Correct 146 ms 83244 KB Output is correct
21 Correct 90 ms 60768 KB Output is correct
22 Correct 95 ms 52304 KB Output is correct
23 Correct 141 ms 83272 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 11096 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 14 ms 23896 KB Output is correct
12 Correct 28 ms 31064 KB Output is correct
13 Correct 115 ms 55376 KB Output is correct
14 Correct 150 ms 82512 KB Output is correct
15 Correct 138 ms 82516 KB Output is correct
16 Correct 93 ms 60752 KB Output is correct
17 Correct 108 ms 52596 KB Output is correct
18 Correct 32 ms 31228 KB Output is correct
19 Correct 152 ms 82596 KB Output is correct
20 Correct 146 ms 83244 KB Output is correct
21 Correct 90 ms 60768 KB Output is correct
22 Correct 95 ms 52304 KB Output is correct
23 Correct 141 ms 83272 KB Output is correct
24 Correct 9 ms 8792 KB Output is correct
25 Correct 3297 ms 24128 KB Output is correct
26 Execution timed out 5034 ms 31056 KB Time limit exceeded
27 Halted 0 ms 0 KB -