Submission #339768

#	Time	Username	Problem	Language	Result	Execution time	Memory
339768		Bill_00	Factories (JOI14_factories)	C++14	100 / 100	7405 ms	256612 KiB

factories

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000
#define ff first
#define ss second
#define pb push_back
#include "factories.h"
#define mp make_pair
typedef long long ll; 
using namespace std;
ll maincent,n,a[1000001],b[1000001],d[1000001],k=0,first[1000001],belong[25][1000001],sz[1000001],centroid,nearest[1000001],o=0,p[1000001];
bool vis[1000001];
vector<ll>child[1000001];
vector<ll>pre[1000001];
vector<int>vec;
vector<pair<ll,ll> >adj[1000001];
ll cnt[1000001],K=0,rr[1000001];
void dfs(int node,int par){
	K++;
	cnt[node]=K;
	for(int i=0;i<child[node].size();i++){
		dfs(child[node][i],node);
	}
	rr[node]=K;
}
void dfs1(ll node,ll par){
  sz[node]=1;
  for(int i=0;i<adj[node].size();i++){
    if(adj[node][i].ff!=par && vis[adj[node][i].ff]==0){
      dfs1(adj[node][i].ff,node);
      sz[node]+=sz[adj[node][i].ff];
    }
  }
}
void dfs3(ll node,ll par,ll dis,ll cent){
	// cout << cnt[node] << ' ' << cnt[cent] << '\n';
  pre[cent][cnt[node]-cnt[cent]]=dis;
  for(int i=0;i<adj[node].size();i++){
    if(adj[node][i].ff!=par && vis[adj[node][i].ff]==0){
      dfs3(adj[node][i].ff,node,dis+adj[node][i].ss,cent);
    }
  }
}
void dfs2(ll node){
	pre[node].resize(rr[node]-cnt[node]+1);
	dfs3(node,-1,0,node);
	vis[node]=1;
	for(int i=0;i<child[node].size();i++){
		dfs2(child[node][i]);
	}
}
void solve(ll node,ll par,ll level,ll parent){
	// cout << node << '\n';
  o++;
  dfs1(node,par);
  ll cent=node;
  while(1){
    bool f=true;
    for(int i=0;i<adj[cent].size();i++){
      if(sz[adj[cent][i].ff]<sz[cent] && vis[adj[cent][i].ff]==0 && sz[adj[cent][i].ff]*2>sz[node]){
        f=false;
        cent=adj[cent][i].ff;
        break;
      }
    }
    if(f) break;
  }
  if(level==1) maincent=cent;
  centroid=cent;
  // cout << cent << ' ' << level << '\n';
  p[cent]=parent;
  child[parent].pb(cent);
  vis[cent]=1;
  for(int i=0;i<adj[cent].size();i++){
    if(vis[adj[cent][i].ff]==0){
      solve(adj[cent][i].ff,-1,level+1,cent);
    }
  }
}
void Init(int N, int A[], int B[], int D[]) {
  n=(ll)N;
  for(int i=0;i<(N-1);i++){
    a[i]=(ll)A[i];
    b[i]=(ll)B[i];
    d[i]=(ll)D[i];
    adj[a[i]].pb(mp(b[i],d[i]));
    adj[b[i]].pb(mp(a[i],d[i]));
  }
  solve(0,-1,1,-1);
  for(int i=0;i<n;i++){
    nearest[i]=1e18;
  }
  dfs(maincent,-1);
  memset(vis,0,sizeof(vis));
  dfs2(maincent);
}
long long Query(int S, int X[], int T, int Y[]) {
  for(int i=0;i<S;i++){
    int XX=X[i];
    while(XX!=-1){
    	nearest[XX]=min(nearest[XX],pre[XX][cnt[X[i]]-cnt[XX]]);
    	// cout << nearest[XX] << ' ' << XX << '\n';
    	vec.pb(XX);
    	XX=p[XX];
    }
  }
  ll ans=2e18;
  for(int i=0;i<T;i++){
    int YY=Y[i];
    while(YY!=-1){
    	ans=min(ans,nearest[YY]+pre[YY][cnt[Y[i]]-cnt[YY]]);
    	YY=p[YY];
    }
  }
  for(int i=0;i<vec.size();i++){
  	nearest[vec[i]]=1e18;
  }
  vec.clear();
  return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<child[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs1(ll, ll)':
factories.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i=0;i<adj[node].size();i++){
      |               ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs3(ll, ll, ll, ll)':
factories.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<adj[node].size();i++){
      |               ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(ll)':
factories.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<child[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void solve(ll, ll, ll, ll)':
factories.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<adj[cent].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~
factories.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i=0;i<adj[cent].size();i++){
      |               ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for(int i=0;i<vec.size();i++){
      |               ~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67