oj.uz

Submission #551257

# Submission time Handle Problem Language Result Execution time Memory
551257 2022-04-20T07:09:47 Z AmShZ Tropical Garden (IOI11_garden) C++11
69 / 100
 512 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 = 5e5 + 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];
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;
	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 23 ms 47572 KB Output is correct
2 Correct 23 ms 47444 KB Output is correct
3 Correct 24 ms 47476 KB Output is correct
4 Correct 23 ms 47252 KB Output is correct
5 Correct 24 ms 47236 KB Output is correct
6 Correct 24 ms 47700 KB Output is correct
7 Correct 27 ms 47308 KB Output is correct
8 Correct 25 ms 47436 KB Output is correct
9 Correct 27 ms 47904 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47572 KB Output is correct
2 Correct 23 ms 47444 KB Output is correct
3 Correct 24 ms 47476 KB Output is correct
4 Correct 23 ms 47252 KB Output is correct
5 Correct 24 ms 47236 KB Output is correct
6 Correct 24 ms 47700 KB Output is correct
7 Correct 27 ms 47308 KB Output is correct
8 Correct 25 ms 47436 KB Output is correct
9 Correct 27 ms 47904 KB Output is correct
10 Correct 24 ms 47240 KB Output is correct
11 Correct 42 ms 51320 KB Output is correct
12 Correct 84 ms 54924 KB Output is correct
13 Correct 71 ms 64204 KB Output is correct
14 Correct 271 ms 71640 KB Output is correct
15 Correct 252 ms 72292 KB Output is correct
16 Correct 243 ms 66280 KB Output is correct
17 Correct 290 ms 64432 KB Output is correct
18 Correct 77 ms 54900 KB Output is correct
19 Correct 255 ms 71740 KB Output is correct
20 Correct 267 ms 72264 KB Output is correct
21 Correct 257 ms 66384 KB Output is correct
22 Correct 243 ms 64468 KB Output is correct
23 Correct 239 ms 73856 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47572 KB Output is correct
2 Correct 23 ms 47444 KB Output is correct
3 Correct 24 ms 47476 KB Output is correct
4 Correct 23 ms 47252 KB Output is correct
5 Correct 24 ms 47236 KB Output is correct
6 Correct 24 ms 47700 KB Output is correct
7 Correct 27 ms 47308 KB Output is correct
8 Correct 25 ms 47436 KB Output is correct
9 Correct 27 ms 47904 KB Output is correct
10 Correct 24 ms 47240 KB Output is correct
11 Correct 42 ms 51320 KB Output is correct
12 Correct 84 ms 54924 KB Output is correct
13 Correct 71 ms 64204 KB Output is correct
14 Correct 271 ms 71640 KB Output is correct
15 Correct 252 ms 72292 KB Output is correct
16 Correct 243 ms 66280 KB Output is correct
17 Correct 290 ms 64432 KB Output is correct
18 Correct 77 ms 54900 KB Output is correct
19 Correct 255 ms 71740 KB Output is correct
20 Correct 267 ms 72264 KB Output is correct
21 Correct 257 ms 66384 KB Output is correct
22 Correct 243 ms 64468 KB Output is correct
23 Correct 239 ms 73856 KB Output is correct
24 Correct 28 ms 48980 KB Output is correct
25 Runtime error 512 ms 262144 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -