oj.uz

Submission #67510

# Submission time Handle Problem Language Result Execution time Memory
67510 2018-08-14T12:31:07 Z IvanC Regions (IOI09_regions) C++11
0 / 100
 163 ms 32076 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 16 ms 14328 KB Time limit exceeded (wall clock)
2 Execution timed out 15 ms 14388 KB Time limit exceeded (wall clock)
3 Execution timed out 16 ms 14464 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 14540 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 14616 KB Time limit exceeded (wall clock)
6 Execution timed out 16 ms 14616 KB Time limit exceeded (wall clock)
7 Execution timed out 14 ms 14652 KB Time limit exceeded (wall clock)
8 Execution timed out 16 ms 14780 KB Time limit exceeded (wall clock)
9 Execution timed out 18 ms 15036 KB Time limit exceeded (wall clock)
10 Execution timed out 17 ms 15204 KB Time limit exceeded (wall clock)
11 Execution timed out 24 ms 15420 KB Time limit exceeded (wall clock)
12 Execution timed out 25 ms 15932 KB Time limit exceeded (wall clock)
13 Execution timed out 26 ms 15932 KB Time limit exceeded (wall clock)
14 Execution timed out 32 ms 16188 KB Time limit exceeded (wall clock)
15 Execution timed out 38 ms 18108 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 47 ms 19132 KB Time limit exceeded (wall clock)
2 Execution timed out 55 ms 19132 KB Time limit exceeded (wall clock)
3 Execution timed out 56 ms 20796 KB Time limit exceeded (wall clock)
4 Execution timed out 31 ms 20796 KB Time limit exceeded (wall clock)
5 Execution timed out 36 ms 20796 KB Time limit exceeded (wall clock)
6 Execution timed out 47 ms 20796 KB Time limit exceeded (wall clock)
7 Execution timed out 66 ms 20796 KB Time limit exceeded (wall clock)
8 Execution timed out 70 ms 22588 KB Time limit exceeded (wall clock)
9 Execution timed out 119 ms 23612 KB Time limit exceeded (wall clock)
10 Execution timed out 105 ms 27500 KB Time limit exceeded (wall clock)
11 Execution timed out 129 ms 27500 KB Time limit exceeded (wall clock)
12 Execution timed out 151 ms 27500 KB Time limit exceeded (wall clock)
13 Execution timed out 128 ms 27500 KB Time limit exceeded (wall clock)
14 Execution timed out 163 ms 27500 KB Time limit exceeded (wall clock)
15 Execution timed out 157 ms 28600 KB Time limit exceeded (wall clock)
16 Execution timed out 137 ms 32076 KB Time limit exceeded (wall clock)
17 Execution timed out 123 ms 32076 KB Time limit exceeded (wall clock)