Submission #551309

#	Time	Username	Problem	Language	Result	Execution time	Memory
551309		alireza_kaviani	Tropical Garden (IOI11_garden)	C++17	100 / 100	2869 ms	61204 KiB

garden

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

#define sep   " "
#define SZ(x) int((x).size())

const int MAXN = 3e5 + 10;

int n , m , p , nxt[MAXN] , V[MAXN] , U[MAXN] , comp[MAXN] , mark[MAXN] , H[MAXN] , ind[MAXN] , valid[MAXN] , first[MAXN];
vector<int> E[MAXN] , vec , cycle[MAXN] , adj[MAXN] , par[MAXN];

void PreDFS(int v){
	mark[v] = 1;
	if(!mark[nxt[v]]){
		PreDFS(nxt[v]);
	}
	vec.push_back(v);
}

void DFS(int v , int cmp , int root , int h = 0){
	if(valid[v])	vec.push_back(h);
	par[v] = vec;
	H[v] = h; comp[v] = cmp; ind[v] = root;
	for(int u : adj[v]){
		if(comp[u] != -1)	continue;
		DFS(u , cmp , root , h + 1);
	}
	if(valid[v])	vec.pop_back();
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	fill(comp , comp + MAXN , -1);
	fill(first , first + MAXN , -1);
	n = N; m = M; p = P;
	for(int i = 0 ; i < m ; i++){
		V[i] = R[i][0]; U[i] = R[i][1];
		E[V[i]].push_back(2 * i);
		E[U[i]].push_back(2 * i + 1);
		if(first[V[i]] == -1){
			first[V[i]] = 2 * i + 1;
		}
		if(first[U[i]] == -1){
			first[U[i]] = 2 * i;
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 1 ; j < SZ(E[i]) ; j++){
			nxt[E[i][j]] = (E[i][0] ^ 1);
		}
		nxt[E[i][0]] = (E[i][1 % SZ(E[i])] ^ 1);
	}
	for(int i : E[p]){
		valid[i] = 1;
	}
	for(int i = 0 ; i < 2 * m ; i++){
		adj[nxt[i]].push_back(i);
//		cout << i << sep << nxt[i] << endl;
	}
	for(int i = 0 ; i < 2 * m ; i++){
		if(comp[i] != -1)	continue;
		vec.clear();
		PreDFS(i);
		int v = vec[0];
		while(comp[v] == -1){
			comp[v] = i;
			cycle[i].push_back(v);
			v = nxt[v];
		}
		for(int j = 0 ; j < SZ(cycle[i]) ; j++){
			vec.clear();
			DFS(cycle[i][j] , i , j , 0);
		}
	}
	for(int i = 0 ; i < Q ; i++){
		int k = G[i] - 1 , ans = 0;
		for(int j = 0 ; j < n ; j++){
			int e = first[j];
			if(H[e] <= k){
				int x = cycle[comp[e]][(k - H[e] + ind[e]) % SZ(cycle[comp[e]])];
				ans += valid[x];
//				cout << j << sep << e << sep << x << sep << valid[x] << endl;
			}
			else{
//				cout << "Debug " << j << endl;
				for(int x : par[e]){
					if(H[e] - x == k){
						ans++;
					}
				}
			}
		}
//		cout << ans << endl;
		answer(ans);
	}
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31