oj.uz

Submission #551256

# Submission time Handle Problem Language Result Execution time Memory
551256 2022-04-20T07:07:56 Z AmShZ Tropical Garden (IOI11_garden) C++11
69 / 100
 500 ms 262144 KB 
//khodaya khodet komak kon
# include "gardenlib.h"
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

struct edge{
	int from, to, tabe;
};

int n, ptr, ans[xn];
edge E[xn];
pii a[xn];
vector <int> adj[2][xn], g[xn], jad;
vector <pii> que[xn];
bool is_good[xn], mark[xn];
deque <int> dq;

void DFS(int v){
	dq.push_back(v);
	if (mark[v])
		return;
	mark[v] = true;
	DFS(E[v].tabe);
}
void DFS2(int v, int rt, int h = 0){
	jad.push_back(v);
	mark[v] = true;
	a[v] = {h, rt};
	for (pii x : que[v]){
		int k = x.A, id = x.B;
		if (k < h)
			ans[id] += is_good[jad[h - k]];
		else{
			k -= h;
			k = (k + rt) % SZ(dq);
			ans[id] += is_good[dq[k]];
		}
	}
	for (int u : g[v]){
		if (mark[u])
			continue;
		DFS2(u, rt, h + 1);
	}
	jad.pop_back();
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	//int N, M, P, Q;
	//cin >> N >> M >> P;
	n = N;
	for (int i = 0; i < M; ++ i){
		int v, u;
		//cin >> v >> u;
		v = R[i][0], u = R[i][1];

		adj[0][v].push_back(ptr);
		adj[1][u].push_back(ptr);
		E[ptr].from = v;
		E[ptr].to = u;
		ptr ++;

		adj[0][u].push_back(ptr);
		adj[1][v].push_back(ptr);
		E[ptr].from = u;
		E[ptr].to = v;
		ptr ++;
	}
	for (int i = 0; i < n; ++ i)
		sort(all(adj[0][i]));
	for (int i = 0; i < ptr; ++ i){
		int v = E[i].to;
		if (adj[0][v][0] != (i ^ 1))
			E[i].tabe = adj[0][v][0];
		else if (1 < SZ(adj[0][v]))
			E[i].tabe = adj[0][v][1];
		else
			E[i].tabe = adj[0][v][0];
		g[E[i].tabe].push_back(i);
	}
	for (int u : adj[1][P])
		is_good[u] = true;
	//cin >> Q;
	for (int _ = 0; _ < Q; ++ _){
		int k = G[_];
		//cin >> k;
		for (int i = 0; i < n; ++ i){
			int v = adj[0][i][0];
			que[v].push_back({k - 1, _});
		}
	}
	for (int i = 0; i < ptr; ++ i){
		if (mark[i])
			continue;
		dq.clear();
		DFS(i);
		while (dq.front() != dq.back())
			mark[dq.front()] = false, dq.pop_front();
		dq.pop_back();
		for (int j = 0; j < SZ(dq); ++ j){
			int v = dq[j];
			jad.clear();
			DFS2(v, j);
		}
	}
	for (int i = 0; i < Q; ++ i){
		//cout << ans[i] << endl;
		answer(ans[i]);
	}
}
/*
int main(){
	fast_io;

	count_routes();

	return 0;
}
*/
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
*/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 16 ms 28776 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 17 ms 28884 KB Output is correct
7 Correct 14 ms 28552 KB Output is correct
8 Correct 16 ms 28628 KB Output is correct
9 Correct 19 ms 29284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 16 ms 28776 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 17 ms 28884 KB Output is correct
7 Correct 14 ms 28552 KB Output is correct
8 Correct 16 ms 28628 KB Output is correct
9 Correct 19 ms 29284 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 31 ms 32956 KB Output is correct
12 Correct 64 ms 36848 KB Output is correct
13 Correct 60 ms 46616 KB Output is correct
14 Correct 264 ms 55152 KB Output is correct
15 Correct 241 ms 55812 KB Output is correct
16 Correct 253 ms 49748 KB Output is correct
17 Correct 223 ms 47856 KB Output is correct
18 Correct 73 ms 36840 KB Output is correct
19 Correct 256 ms 55236 KB Output is correct
20 Correct 289 ms 55924 KB Output is correct
21 Correct 270 ms 49812 KB Output is correct
22 Correct 248 ms 47820 KB Output is correct
23 Correct 241 ms 57448 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 16 ms 28776 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 17 ms 28884 KB Output is correct
7 Correct 14 ms 28552 KB Output is correct
8 Correct 16 ms 28628 KB Output is correct
9 Correct 19 ms 29284 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 31 ms 32956 KB Output is correct
12 Correct 64 ms 36848 KB Output is correct
13 Correct 60 ms 46616 KB Output is correct
14 Correct 264 ms 55152 KB Output is correct
15 Correct 241 ms 55812 KB Output is correct
16 Correct 253 ms 49748 KB Output is correct
17 Correct 223 ms 47856 KB Output is correct
18 Correct 73 ms 36840 KB Output is correct
19 Correct 256 ms 55236 KB Output is correct
20 Correct 289 ms 55924 KB Output is correct
21 Correct 270 ms 49812 KB Output is correct
22 Correct 248 ms 47820 KB Output is correct
23 Correct 241 ms 57448 KB Output is correct
24 Correct 20 ms 30164 KB Output is correct
25 Runtime error 500 ms 262144 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -