Submission #62278

#	Time	Username	Problem	Language	Result	Execution time	Memory
62278		Darksinian	Factories (JOI14_factories)	C++14	33 / 100	8045 ms	209312 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int c[500002];
long long d[500002];
int dp2[500002][20];
long long dp[500002][3];
vector<int> E;
int ind[1000002];
int org[1000002];
int L[1000006];
int dp3[1000002][20];
int occ[1000002];
vector<pair<int,long long> > g[500002];

void dfs(int s,int p) {
    dp[s][1] = 1e17;
    dp[s][2] = 1e17;
    if(c[s]) dp[s][c[s]] = 0;
    for(auto u : g[s]) {
        int u1 = u.first;
        if(u1!=p) {
            dfs(u1,s);
            dp[s][1] = min(dp[s][1],dp[u1][1] + u.second);
            dp[s][2] = min(dp[s][2],dp[u1][2] + u.second);
        }
    }
}
int vis[500002];
void bfs() {
queue<int> q;
q.push(1);
int in = 0;
while(!q.empty()) {
in++;
int v = q.front();
ind[v] = in;
org[in] = v;
q.pop();
vis[v] = 1;
for(auto u : g[v]) {
    if(u.first!=v && !vis[u.first]) {
        q.push(u.first);
    }
}
}
}
void dfs3(int s,int p) {
E.push_back(ind[s]);
occ[s] = E.size()-1;
for(auto u : g[s]) {
    if(u.first!=p) {
        d[u.first] = d[s] + u.second;
        dfs3(u.first,s);
        E.push_back(ind[s]);
    }
}
}
void pre2() {
   for(int i =0;i<20;i++){
     for(int j =0;j+(1<<i)-1<E.size();j++){
        if(!i) dp3[j][i] = E[j];
        else dp3[j][i] = min(dp3[j][i-1],dp3[j + (1<<(i-1)) ][i-1]);
     }
   }
}
int qr(int l,int r) {
int k = L[r-l+1];
return min(dp3[l][k],dp3[r-(1<<k)+1][k]);
}
void pretree() {
bfs();
dfs3(1,1);
pre2();
}
int lca(int u,int v){
int ll = occ[u];
int r = occ[v];
int lc = qr(min(ll,r),max(ll,r));
return org[lc];
}
long long dist(int u, int v) {
return d[u] + d[v] - 2*d[lca(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i =0;i<N;i++){
        g[A[i]+1].push_back({B[i]+1,D[i]});
        g[B[i]+1].push_back({A[i]+1,D[i]});
    }
    for(int i =1,j =0;i<1000005;i*=2,j++) L[i] = j;
    for(int i =2;i<1000005;i++) {
        if(!L[i]) L[i] = L[i-1];
    }
    pretree();
}

long long Query(int S, int X[], int T, int Y[]) {

  long long ans = 1e18;
  if(!(S<=20 && T<=20)) {
          for(int i =0;i<S;i++) {
    c[X[i]+1] = 1;
  }
  for(int i =0;i<T;i++){
    c[Y[i]+1] = 2;
  }

        dfs(1,1);
        for(int i =1;i<=n;i++) c[i] = 0;
        for(int i =1;i<=n;i++) {
        ans = min(ans,dp[i][2] + dp[i][1]);
        }
  }
 else {
  for(int i =0;i<S;i++) {
       for(int j =0;j<T;j++) ans = min(ans,dist(X[i]+1,Y[j]+1));
  }
 }
 
  return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void pre2()':
factories.cpp:62:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j =0;j+(1<<i)-1<E.size();j++){
                   ~~~~~~~~~~^~~~~~~~~

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