oj.uz

Submission #851276

# Submission time Handle Problem Language Result Execution time Memory
851276 2023-09-19T09:26:04 Z Halym2007 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 81236 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 9048 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 1 ms 8792 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 3 ms 10840 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 9048 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 1 ms 8792 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 13 ms 23640 KB Output is correct
12 Correct 29 ms 30556 KB Output is correct
13 Correct 124 ms 54352 KB Output is correct
14 Correct 146 ms 80748 KB Output is correct
15 Correct 144 ms 80980 KB Output is correct
16 Correct 92 ms 59368 KB Output is correct
17 Correct 96 ms 50768 KB Output is correct
18 Correct 29 ms 30552 KB Output is correct
19 Correct 148 ms 80932 KB Output is correct
20 Correct 146 ms 80976 KB Output is correct
21 Correct 91 ms 59216 KB Output is correct
22 Correct 106 ms 50768 KB Output is correct
23 Correct 134 ms 81236 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 9048 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 1 ms 8792 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 13 ms 23640 KB Output is correct
12 Correct 29 ms 30556 KB Output is correct
13 Correct 124 ms 54352 KB Output is correct
14 Correct 146 ms 80748 KB Output is correct
15 Correct 144 ms 80980 KB Output is correct
16 Correct 92 ms 59368 KB Output is correct
17 Correct 96 ms 50768 KB Output is correct
18 Correct 29 ms 30552 KB Output is correct
19 Correct 148 ms 80932 KB Output is correct
20 Correct 146 ms 80976 KB Output is correct
21 Correct 91 ms 59216 KB Output is correct
22 Correct 106 ms 50768 KB Output is correct
23 Correct 134 ms 81236 KB Output is correct
24 Correct 10 ms 9036 KB Output is correct
25 Correct 3274 ms 23872 KB Output is correct
26 Execution timed out 5036 ms 30552 KB Time limit exceeded
27 Halted 0 ms 0 KB -