oj.uz

Submission #551207

# Submission time Handle Problem Language Result Execution time Memory
551207 2022-04-20T05:37:41 Z Keshi Tropical Garden (IOI11_garden) C++17
49 / 100
 156 ms 46720 KB 
//In the name of God
#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll INF = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

int n, a[maxn], dis[maxn];
int cnt[2][maxn], dor[2];
bool vis[maxn];
vector<int> g[maxn], gp[maxn];

void dfs(int v){
	vis[v] = 1;
	for(int u : gp[v]){
		if(vis[u]) continue;
		dis[u] = dis[v] + 1;
		dfs(u);
	}
	return;
}

void Do(int x, int f){
	memset(dis, -1, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[x] = 0;
	dfs(x);
	for(int i = 0; i < (n << 1); i += 2){
		if(~dis[i]) cnt[f][dis[i]]++;
	}
	dor[f] = -1;
	if(dis[a[x]] == -1) return;
	int t = dis[a[x]] + 1;
	dor[f] = t;
	for(int i = t; i < maxn; i++){
		cnt[f][i] += cnt[f][i - t];
	}
	return;
}

void count_routes(int N, int m, int p, int R[][2], int Q, int G[]){
	n = N;
	for(int i = 0; i < m; i++){
		int v = R[i][0], u = R[i][1];
		g[v].pb(u);
		g[u].pb(v);
	}
	for(int i = 0; i < n; i++){
		int v = g[i][0];
		if(g[v][0] == i) a[i << 1] = (v << 1) | 1;
		else a[i << 1] = v << 1;
		if(Sz(g[i]) == 1){
			a[i << 1 | 1] = a[i << 1];
			continue;
		}
		v = g[i][1];
		if(g[v][0] == i) a[i << 1 | 1] = (v << 1) | 1;
		else a[i << 1 | 1] = v << 1;
	}
	for(int i = 0; i < (n << 1); i++){
		gp[a[i]].pb(i);
	}
	Do(p << 1, 0);
	Do(p << 1 | 1, 1);
	for(int i = 0; i < Q; i++){
		int x = G[i];
		int ans = 0;
		if(dor[0] == -1){
			if(x < maxn) ans += cnt[0][x];
		}
		else{
			while(x >= maxn) x -= dor[0];
			ans += cnt[0][x];
		}
		if(dor[1] == -1){
			if(x < maxn) ans += cnt[1][x];
		}
		else{
			while(x >= maxn) x -= dor[1];
			ans += cnt[1][x];
		}
		answer(ans);
	}
	return;
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30292 KB Output is correct
2 Correct 16 ms 30288 KB Output is correct
3 Correct 16 ms 30292 KB Output is correct
4 Correct 14 ms 28116 KB Output is correct
5 Correct 15 ms 28128 KB Output is correct
6 Correct 17 ms 30344 KB Output is correct
7 Correct 16 ms 30184 KB Output is correct
8 Correct 16 ms 30240 KB Output is correct
9 Correct 19 ms 30420 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30292 KB Output is correct
2 Correct 16 ms 30288 KB Output is correct
3 Correct 16 ms 30292 KB Output is correct
4 Correct 14 ms 28116 KB Output is correct
5 Correct 15 ms 28128 KB Output is correct
6 Correct 17 ms 30344 KB Output is correct
7 Correct 16 ms 30184 KB Output is correct
8 Correct 16 ms 30240 KB Output is correct
9 Correct 19 ms 30420 KB Output is correct
10 Correct 16 ms 30080 KB Output is correct
11 Correct 25 ms 32140 KB Output is correct
12 Correct 36 ms 33484 KB Output is correct
13 Correct 53 ms 46720 KB Output is correct
14 Correct 113 ms 42828 KB Output is correct
15 Correct 156 ms 43312 KB Output is correct
16 Correct 88 ms 39996 KB Output is correct
17 Correct 104 ms 36964 KB Output is correct
18 Correct 37 ms 30084 KB Output is correct
19 Correct 120 ms 42856 KB Output is correct
20 Correct 153 ms 43224 KB Output is correct
21 Correct 85 ms 38064 KB Output is correct
22 Incorrect 94 ms 38976 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30292 KB Output is correct
2 Correct 16 ms 30288 KB Output is correct
3 Correct 16 ms 30292 KB Output is correct
4 Correct 14 ms 28116 KB Output is correct
5 Correct 15 ms 28128 KB Output is correct
6 Correct 17 ms 30344 KB Output is correct
7 Correct 16 ms 30184 KB Output is correct
8 Correct 16 ms 30240 KB Output is correct
9 Correct 19 ms 30420 KB Output is correct
10 Correct 16 ms 30080 KB Output is correct
11 Correct 25 ms 32140 KB Output is correct
12 Correct 36 ms 33484 KB Output is correct
13 Correct 53 ms 46720 KB Output is correct
14 Correct 113 ms 42828 KB Output is correct
15 Correct 156 ms 43312 KB Output is correct
16 Correct 88 ms 39996 KB Output is correct
17 Correct 104 ms 36964 KB Output is correct
18 Correct 37 ms 30084 KB Output is correct
19 Correct 120 ms 42856 KB Output is correct
20 Correct 153 ms 43224 KB Output is correct
21 Correct 85 ms 38064 KB Output is correct
22 Incorrect 94 ms 38976 KB Output isn't correct
23 Halted 0 ms 0 KB -