oj.uz

Submission #67502

# Submission time Handle Problem Language Result Execution time Memory
67502 2018-08-14T11:20:40 Z IvanC Regions (IOI09_regions) C++17
0 / 100
 159 ms 32160 KB 
// Ivan Carvalho
// Regions - IOI 2009
// O(N*sqrt(Q))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 2*1e5 + 10;

//Declarando as variáveis
vector<int> grafo[MAXN],regioes[MAXN];
vector<ii> perguntas[MAXN];
int ini[MAXN],fim[MAXN],dfsPtr,cor[MAXN],freq[MAXN],pesado[MAXN],sz[MAXN],vetor[MAXN],N,R,Q;
ll tot[MAXN],exibe[MAXN];

// Utilidades para o Sack
void add(int v){
	freq[cor[v]]++;
}
void remove(int v){
	freq[cor[v]]--;
}
// Calculando o tamanho das sub-árvores

int dfs1(int v){
	ini[v] = ++dfsPtr;
	vetor[ini[v]] = v;
	sz[v] = 1;
	for(int u : grafo[v]){
		sz[v] += dfs1(u);
	}
	fim[v] = dfsPtr;
	return sz[v];
}

// Rodando o Sack
void dfs2(int v,int keep){
	// Big guarda o filho de maior tamanho
	int big = -1,mx = 0;
	for(int u : grafo[v]){
		if(sz[u] > mx){
			big = u;
			mx = sz[u];
		}
	}
	// Não salvamos as informações dos filhos que não são o maior
	for(int u : grafo[v]){
		if(u != big) dfs2(u,0);
	}
	// Caso exista o maior, salvamos sua informação
	if(big != -1) dfs2(big,1);
	add(v);
	// Adicionamos as informações dos filhos menores
	for(int u : grafo[v]){
		if(u == big) continue;
		for(int i = ini[u];i<=fim[u];i++){
			add(vetor[i]);
		}
	}
	// Caso não haja muitas perguntas na região, ajudamos a responder-las agora 
	if(!pesado[cor[v]]){
		for(ii par : perguntas[cor[v]]){
			exibe[par.second] += freq[par.first];
		}
	}
	// Se não devemos guardar a informação desse vértice, limpamos
	if(keep == 0){
		for(int i = ini[v];i<=fim[v];i++){
			remove(vetor[i]);
		}
	}
}

// No caso das regiões com muitas queries, processamos suas perguntas separadamente
void processa_heavy(int familia){
	// Limpamos os arrays
	memset(freq,0,sizeof(freq));
	memset(tot,0,sizeof(tot));
	// Fazemos a soma acumulada no vetor da árvore
	for(int v : regioes[familia]){
		freq[ini[v]]++;
		freq[fim[v]+1]--;
	}
	for(int i = 1;i<=N;i++){
		freq[i] += freq[i-1];
	}
	// Adicionamos quantos ancestrais de i são dessa região
	for(int i = 1;i<=N;i++){
		tot[cor[i]] += 1LL*freq[ini[i]];
	}
	// Respondemos as queries
	for(ii par : perguntas[familia]){
		exibe[par.second] = tot[par.first];
	}
}

int main(){
	// Leemos a entrada
	scanf("%d %d %d",&N,&R,&Q);
	scanf("%d",&cor[1]);
	regioes[cor[1]].push_back(1);
	for(int i = 2;i<=N;i++){
		int s;
		scanf("%d %d",&s,&cor[i]);
		grafo[s].push_back(i);
		regioes[cor[i]].push_back(i);
	}
	// Rodamos o primeiro dfs e lemos a entrada
	dfs1(1);
	for(int i = 1;i<=Q;i++){
		int r1,r2;
		scanf("%d %d",&r1,&r2);
		perguntas[r1].push_back(ii(r2,i));
	}
	// Sqrt-decomposition e Sack
	int bucket = (int)ceil(sqrt(Q));
	for(int i = 1;i<=R;i++){
		if(perguntas[i].size() >= bucket) pesado[i] = 1;
	}
	dfs2(1,0);
	for(int i = 1;i<=R;i++){
		if(pesado[i]) processa_heavy(i);
	}
	// Exibimos a resposta
	for(int i = 1;i<=Q;i++) printf("%lld\n",exibe[i]);
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:118:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(perguntas[i].size() >= bucket) pesado[i] = 1;
      ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
regions.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&R,&Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&cor[1]);
  ~~~~~^~~~~~~~~~~~~~
regions.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&cor[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&r1,&r2);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 13 ms 14328 KB Time limit exceeded (wall clock)
2 Execution timed out 14 ms 14392 KB Time limit exceeded (wall clock)
3 Execution timed out 17 ms 14464 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 14624 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 14652 KB Time limit exceeded (wall clock)
6 Execution timed out 15 ms 14652 KB Time limit exceeded (wall clock)
7 Execution timed out 15 ms 14708 KB Time limit exceeded (wall clock)
8 Execution timed out 13 ms 14728 KB Time limit exceeded (wall clock)
9 Execution timed out 14 ms 14984 KB Time limit exceeded (wall clock)
10 Execution timed out 18 ms 15112 KB Time limit exceeded (wall clock)
11 Execution timed out 17 ms 15412 KB Time limit exceeded (wall clock)
12 Execution timed out 22 ms 15924 KB Time limit exceeded (wall clock)
13 Execution timed out 26 ms 15924 KB Time limit exceeded (wall clock)
14 Execution timed out 39 ms 16188 KB Time limit exceeded (wall clock)
15 Execution timed out 29 ms 18108 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 50 ms 19132 KB Time limit exceeded (wall clock)
2 Execution timed out 50 ms 19132 KB Time limit exceeded (wall clock)
3 Execution timed out 48 ms 20704 KB Time limit exceeded (wall clock)
4 Execution timed out 26 ms 20704 KB Time limit exceeded (wall clock)
5 Execution timed out 33 ms 20704 KB Time limit exceeded (wall clock)
6 Execution timed out 54 ms 20704 KB Time limit exceeded (wall clock)
7 Execution timed out 64 ms 20704 KB Time limit exceeded (wall clock)
8 Execution timed out 76 ms 22592 KB Time limit exceeded (wall clock)
9 Execution timed out 98 ms 23704 KB Time limit exceeded (wall clock)
10 Execution timed out 109 ms 27476 KB Time limit exceeded (wall clock)
11 Execution timed out 122 ms 27476 KB Time limit exceeded (wall clock)
12 Execution timed out 142 ms 27476 KB Time limit exceeded (wall clock)
13 Execution timed out 114 ms 27476 KB Time limit exceeded (wall clock)
14 Execution timed out 159 ms 27476 KB Time limit exceeded (wall clock)
15 Execution timed out 129 ms 28508 KB Time limit exceeded (wall clock)
16 Execution timed out 152 ms 32160 KB Time limit exceeded (wall clock)
17 Execution timed out 127 ms 32160 KB Time limit exceeded (wall clock)