oj.uz

Submission #36487

# Submission time Handle Problem Language Result Execution time Memory
36487 2017-12-09T22:42:26 Z IvanC Factories (JOI14_factories) C++14
15 / 100
 6000 ms 197396 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const int MAXN = 5*1e5 + 10;
const ll INF = 1e18;
vector<ii> grafo[MAXN];
vector<int> ctree[MAXN];
ll dist[MAXN][25];
int pai[MAXN],block[MAXN],sz[MAXN],tam,iteracao,versao[MAXN],ptr[MAXN];
ll minimo[MAXN];
int dfs1(int v,int p){
	sz[v] = 1;
	for(int i = 0;i<grafo[v].size();i++){
		int u = grafo[v][i].first;
		if(u == p || block[u]) continue;
		sz[v] += dfs1(u,v);
	}
	return sz[v];
}
void dfs2(int v,int p,ii &resp){
	int mx = tam - sz[v];
	for(int i = 0;i<grafo[v].size();i++){
		int u = grafo[v][i].first;
		if(u == p || block[u]) continue;
		dfs2(u,v,resp);
		mx = max(mx,sz[u]);
	}
	ii davez = ii(mx,v);
	resp = min(resp, davez );
}
void dfs3(int v,int p,ll depth){
	dist[v][ptr[v]++] = depth;
	for(int i = 0;i<grafo[v].size();i++){
		int u = grafo[v][i].first;
		ll w = (ll)grafo[v][i].second;
		if(u == p || block[u]) continue;
		dfs3(u,v,depth + w);
	}
}
int find_centroid(int v){
	tam = dfs1(v,-1);
	ii resp = ii(tam+1,tam+1);
	dfs2(v,-1,resp);
	v = resp.second;
	dfs3(v,-1,0);
	return v;
}
int decompoe(int v){
	v = find_centroid(v);
	block[v] = 1;
	for(int i = 0;i<grafo[v].size();i++){
		int u = grafo[v][i].first;
		if(block[u]) continue;
		u = decompoe(u);
		ctree[u].push_back(v);
		ctree[v].push_back(u);
	}
	return v;
}
void dfs4(int v,int p){
	pai[v] = p;
	for(int u : ctree[v]){
		if(u == p) continue;
		dfs4(u,v);
	}
}
void insere(int v){
	int x = v;
	for(int nivel = ptr[x] - 1;nivel>=0;nivel--){
		if(versao[v] != iteracao){
			versao[v] = iteracao;
			minimo[v] = dist[x][nivel];
		}
		else{
			minimo[v] = min(minimo[v], dist[x][nivel] );
		}
		v = pai[v];
	}
}
ll queryup(int v){
	ll resp = INF;
	int x = v;
	for(int nivel = ptr[x] - 1;nivel>=0;nivel--){
		if(versao[v] == iteracao) resp = min(resp, minimo[v] + dist[x][nivel] );
		v = pai[v];
	}
	return resp;
}
void Init(int N, int A[], int B[], int D[]){
	for(int i = 0;i<=N-2;i++){
		grafo[A[i]].push_back(ii(B[i],D[i]));
		grafo[B[i]].push_back(ii(A[i],D[i]));
	}
	int raiz = decompoe(0);
	dfs4(raiz,-1);
}
long long Query(int S, int X[], int T, int Y[]){
	ll resp = INF;
	iteracao++;
	for(int i = 0;i<=S-1;i++){
		insere(X[i]);
	}
	for(int i = 0;i<=T-1;i++){
		resp = min(resp, queryup(Y[i]) );
	}
	return resp;
}

Compilation message

factories.cpp: In function 'int dfs1(int, int)':
factories.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                 ^
factories.cpp: In function 'void dfs2(int, int, ii&)':
factories.cpp:24:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                 ^
factories.cpp: In function 'void dfs3(int, int, ll)':
factories.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                 ^
factories.cpp: In function 'int decompoe(int)':
factories.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 159052 KB Output is correct
2 Correct 356 ms 159448 KB Output is correct
3 Correct 406 ms 159448 KB Output is correct
4 Correct 419 ms 159448 KB Output is correct
5 Correct 393 ms 159540 KB Output is correct
6 Correct 379 ms 159484 KB Output is correct
7 Correct 423 ms 159448 KB Output is correct
8 Correct 433 ms 159448 KB Output is correct
9 Correct 443 ms 159536 KB Output is correct
10 Correct 319 ms 159484 KB Output is correct
11 Correct 386 ms 159448 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 159052 KB Output is correct
2 Correct 4146 ms 194032 KB Output is correct
3 Execution timed out 6000 ms 197396 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4533 ms 194032 KB Output is correct
2 Correct 4253 ms 194032 KB Output is correct
3 Execution timed out 6000 ms 196168 KB Execution timed out
4 Halted 0 ms 0 KB -