Submission #36486

#	Time	Username	Problem	Language	Result	Execution time	Memory
36486		IvanC	Factories (JOI14_factories)	C++14	15 / 100	6000 ms	210228 KiB

factories

#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];
vector<ll> dist[MAXN];
int pai[MAXN],block[MAXN],sz[MAXN],tam,iteracao,versao[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].push_back(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 = dist[x].size()-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 = dist[x].size()-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 (stderr)

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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67