oj.uz

Submission #551205

# Submission time Handle Problem Language Result Execution time Memory
551205 2022-04-20T05:31:40 Z Keshi Tropical Garden (IOI11_garden) C++17
49 / 100
 67 ms 34892 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 = 3e5 + 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);
	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 10 ms 18004 KB Output is correct
2 Correct 11 ms 18004 KB Output is correct
3 Correct 10 ms 18000 KB Output is correct
4 Correct 10 ms 16708 KB Output is correct
5 Correct 12 ms 16708 KB Output is correct
6 Correct 11 ms 18108 KB Output is correct
7 Correct 11 ms 17848 KB Output is correct
8 Correct 11 ms 18004 KB Output is correct
9 Correct 12 ms 18264 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18004 KB Output is correct
2 Correct 11 ms 18004 KB Output is correct
3 Correct 10 ms 18000 KB Output is correct
4 Correct 10 ms 16708 KB Output is correct
5 Correct 12 ms 16708 KB Output is correct
6 Correct 11 ms 18108 KB Output is correct
7 Correct 11 ms 17848 KB Output is correct
8 Correct 11 ms 18004 KB Output is correct
9 Correct 12 ms 18264 KB Output is correct
10 Correct 11 ms 17876 KB Output is correct
11 Correct 19 ms 20188 KB Output is correct
12 Correct 34 ms 21816 KB Output is correct
13 Incorrect 67 ms 34892 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18004 KB Output is correct
2 Correct 11 ms 18004 KB Output is correct
3 Correct 10 ms 18000 KB Output is correct
4 Correct 10 ms 16708 KB Output is correct
5 Correct 12 ms 16708 KB Output is correct
6 Correct 11 ms 18108 KB Output is correct
7 Correct 11 ms 17848 KB Output is correct
8 Correct 11 ms 18004 KB Output is correct
9 Correct 12 ms 18264 KB Output is correct
10 Correct 11 ms 17876 KB Output is correct
11 Correct 19 ms 20188 KB Output is correct
12 Correct 34 ms 21816 KB Output is correct
13 Incorrect 67 ms 34892 KB Output isn't correct
14 Halted 0 ms 0 KB -