oj.uz

Submission #49285

# Submission time Handle Problem Language Result Execution time Memory
49285 2018-05-25T01:49:02 Z wzy Factories (JOI14_factories) C++11
15 / 100
 6000 ms 205616 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pii pair<int,long long>
#define F first
#define S second
#define pb push_back
bool jafoi[500005];
vector<pii> adj[500005] , vt[500005];
int n , pai[500005] , lca[22][500005] , depth[500005] , st[500005] , t= 0 , ed[500005] ;
long long  dist[500005] , dp[2][500005];
void pre_dfs(int x , int y){
	pai[x] = y;
	st[x] = ++t;
	for(int j = 0 ; j < adj[x].size() ; j++){
		pii u = adj[x][j];
		if(u.first == y) continue;
		dist[u.first] = dist[x] + u.second;
		depth[u.first] = depth[x] + 1;
		pre_dfs(u.first, x);
	}
	ed[x] = t;
}
 
int query_lca(int x , int y){
	if(depth[x] > depth[y]) swap(x,y);
	for(int j = 21 ; j >= 0 ; j--){
		int u = depth[y] - (1<<j);
		if(u >= depth[x]){
			y = lca[j][y];
		}
	}
	if(x == y) return x;
	for(int j = 21 ; j >= 0 ; j--){
		if(lca[j][x] != lca[j][y] && lca[j][x] != -1){
			x = lca[j][x] , y = lca[j][y];
		}
	}
	return pai[x];
}
 
inline long long distance_query(int x , int y){
	return(dist[x] + dist[y] - 2*dist[query_lca(x,y)]);
}
 
 
void Init(int N, int A[], int B[], int D[]){
	n = N;
	for(int i = 0 ; i < N - 1 ; i++){
		adj[A[i]].pb(pii(B[i] , D[i]));
		adj[B[i]].pb(pii(A[i] , D[i]));
	}
	depth[0] = 0 , dist[0] = 0;
	pre_dfs(0 , - 1 );
	pai[0] = -1;
	for(int i = 0 ; i < N ; i++){
		lca[0][i] = pai[i];
	}
	for(int j = 1 ; j < 22 ; j++){
		for(int i = 0 ; i < N ; i++){
			lca[j][i] = lca[j-1][lca[j-1][i]];
		}
	}
}
 
bool cmp(int a , int  b){
	return st[a] < st[b];
}
 
long long ansz = 0;
 
void solve(int x , int y){
	for(int j = 0 ; j < vt[x].size() ; j++){
		pii u = vt[x][j];
		if(u.F == y) continue;
		solve(u.F, x);
		ansz = min(ansz , min(dp[0][x] + dp[1][u.F] + u.S ,  dp[1][x] + dp[0][u.F] + u.S));
		dp[0][x] = min(dp[0][x] , dp[0][u.F] + u.S);
		dp[1][x] = min(dp[1][x] , dp[1][u.F] + u.S);
	}
	return ;
}
 
long long Query(int S , int X[] , int T , int Y[]){
	vector<int> op;
	for(int i = 0 ; i < S ;i ++){
		if(!jafoi[X[i]]){
		op.push_back(X[i]);
		jafoi[X[i]] = 1;
	}
	}
	for(int i = 0 ; i < T ;i ++){
		if(!jafoi[Y[i]]){
		op.push_back(Y[i]);
		jafoi[Y[i]] = 1;
	}
	}
	sort(op.begin() , op.end() , cmp);
	int Z = ((int)op.size())- 1;
	for(int i = 0 ; i < Z ; i++){
		int L = query_lca(op[i] , op[i+1]);
		if(!jafoi[L]){
		op.push_back(L);		
		jafoi[L] = 1;
		}
	}
	sort(op.begin() , op.end() ,cmp);
	stack<int> w;
	int root = 0;
	for(int i = 0 ; i < op.size() ; i++){
		dp[0][op[i]] =  1000000000000000LL;
		dp[1][op[i]] =  1000000000000000LL;
		if(w.empty()) w.push(op[i]) , root = op[i];
		else{
			while(w.size() && !(st[w.top()] <= st[op[i]] && st[op[i]] <= ed[w.top()])){
				w.pop();
			}
			long long u = distance_query(w.top() , op[i]);
			vt[op[i]].push_back(pii(w.top() , u));
			vt[w.top()].push_back(pii(op[i] , u));
			w.push(op[i]);
		}
	}
	for(int i = 0 ; i < S ; i++) dp[0][X[i]] = 0;
	for(int i = 0 ; i < T ; i++) dp[1][Y[i]] = 0;
	ansz = 1000000000000000LL;
	solve(root , root);
	for(int i = 0 ; i < op.size() ; i++){
		vt[op[i]].clear();
		jafoi[op[i]] = false;
	}
	return ansz;
}

Compilation message

factories.cpp: In function 'void pre_dfs(int, int)':
factories.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < adj[x].size() ; j++){
                  ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void solve(int, int)':
factories.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < vt[x].size() ; j++){
                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < op.size() ; i++){
                  ~~^~~~~~~~~~~
factories.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < op.size() ; i++){
                  ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 24440 KB Output is correct
2 Correct 1308 ms 33380 KB Output is correct
3 Correct 1579 ms 33380 KB Output is correct
4 Correct 1942 ms 33748 KB Output is correct
5 Correct 1329 ms 33748 KB Output is correct
6 Correct 1128 ms 33748 KB Output is correct
7 Correct 1551 ms 33748 KB Output is correct
8 Correct 1409 ms 33748 KB Output is correct
9 Correct 1302 ms 33976 KB Output is correct
10 Correct 1162 ms 33976 KB Output is correct
11 Correct 1770 ms 33976 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33976 KB Output is correct
2 Correct 4096 ms 140432 KB Output is correct
3 Correct 5722 ms 142488 KB Output is correct
4 Correct 2565 ms 156124 KB Output is correct
5 Correct 3798 ms 202628 KB Output is correct
6 Execution timed out 6021 ms 202628 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6043 ms 205616 KB Time limit exceeded
2 Halted 0 ms 0 KB -