oj.uz

Submission #233085

# Submission time Handle Problem Language Result Execution time Memory
233085 2020-05-19T09:16:12 Z crossing0ver Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 87544 KB 
#include<bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"
using namespace std;

pair<int,int> D[150001][31][2];
pair<int,int> mn[150001][2];

vector<pair<int,int>> adj[150001];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	P++;
	for (int i = 0; i < M; i++) {
		R[i][0]++;
		R[i][1]++;
		adj[R[i][0]].push_back({R[i][1],i + 1});
		adj[R[i][1]].push_back({R[i][0],i+1});
	}
	for (int i = 1; i <= N; i++) {
		 if (adj[i].size() == 1) mn[i][0] = {adj[i][0].second,adj[i][0].first}, mn[i][1] = {adj[i][0].second,adj[i][0].first};
		else mn[i][0] = {adj[i][0].second,adj[i][0].first}, mn[i][1] = {adj[i][1].second,adj[i][1].first};
	}
	for (int i = 1; i <= N; i++) {
		D[i][0][0] = {mn[i][0].second,mn[i][0].first};
		D[i][0][1] = {mn[i][1].second,mn[i][1].first};
	}
		for (int j = 1; j <= 30; j++) {
			for (int i = 1; i <= N; i++) {
				auto S = D[i][j-1][0];
				int x = S.first;
				int val = S.second;
				if (val == mn[x][0].first) {
					D[i][j][0] = D[x][j-1][1];
				}
				else D[i][j][0] = D[x][j-1][0];
				 S = D[i][j-1][1];
				 x = S.first;
				 val = S.second;
				if (val == mn[x][0].first) 
					D[i][j][1] = D[x][j-1][1];
				else D[i][j][1] = D[x][j-1][0];
			}
		}
	
    for (int q = 0,k; q < Q; q++) {
    	k = G[q];
    	pair<int,int> cur;
    	int ans  = 0;
    	for (int i = 1; i <= N; i++) {
    		 cur = {i,0};
    	for (int j = 0; j <= 30; j++)
    	if (k & (1<< j) ) {
    		if (cur.second != mn[cur.first][0].first)
    			cur = D[cur.first][j][0];
    		else cur = D[cur.first][j][1];
    	}
    	if (cur.first == P) ans ++;	
    	}      
       answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3968 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 6 ms 3968 KB Output is correct
8 Correct 7 ms 4480 KB Output is correct
9 Correct 9 ms 4736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3968 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 6 ms 3968 KB Output is correct
8 Correct 7 ms 4480 KB Output is correct
9 Correct 9 ms 4736 KB Output is correct
10 Correct 7 ms 3968 KB Output is correct
11 Correct 31 ms 16384 KB Output is correct
12 Correct 53 ms 25464 KB Output is correct
13 Correct 173 ms 50936 KB Output is correct
14 Correct 223 ms 79480 KB Output is correct
15 Correct 223 ms 80576 KB Output is correct
16 Correct 156 ms 57080 KB Output is correct
17 Correct 142 ms 49316 KB Output is correct
18 Correct 56 ms 25464 KB Output is correct
19 Correct 215 ms 79592 KB Output is correct
20 Correct 223 ms 80636 KB Output is correct
21 Correct 157 ms 56952 KB Output is correct
22 Correct 152 ms 49076 KB Output is correct
23 Correct 249 ms 87544 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 6 ms 3840 KB Output is correct
5 Correct 7 ms 3968 KB Output is correct
6 Correct 7 ms 4480 KB Output is correct
7 Correct 6 ms 3968 KB Output is correct
8 Correct 7 ms 4480 KB Output is correct
9 Correct 9 ms 4736 KB Output is correct
10 Correct 7 ms 3968 KB Output is correct
11 Correct 31 ms 16384 KB Output is correct
12 Correct 53 ms 25464 KB Output is correct
13 Correct 173 ms 50936 KB Output is correct
14 Correct 223 ms 79480 KB Output is correct
15 Correct 223 ms 80576 KB Output is correct
16 Correct 156 ms 57080 KB Output is correct
17 Correct 142 ms 49316 KB Output is correct
18 Correct 56 ms 25464 KB Output is correct
19 Correct 215 ms 79592 KB Output is correct
20 Correct 223 ms 80636 KB Output is correct
21 Correct 157 ms 56952 KB Output is correct
22 Correct 152 ms 49076 KB Output is correct
23 Correct 249 ms 87544 KB Output is correct
24 Correct 16 ms 3968 KB Output is correct
25 Execution timed out 5069 ms 16448 KB Time limit exceeded
26 Halted 0 ms 0 KB -