oj.uz

Submission #62278

# Submission time Handle Problem Language Result Execution time Memory
62278 2018-07-28T01:23:32 Z Darksinian Factories (JOI14_factories) C++14
33 / 100
 8000 ms 209312 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16504 KB Output is correct
2 Correct 657 ms 25644 KB Output is correct
3 Correct 1663 ms 25792 KB Output is correct
4 Correct 1407 ms 25804 KB Output is correct
5 Correct 660 ms 26068 KB Output is correct
6 Correct 417 ms 26068 KB Output is correct
7 Correct 1736 ms 27536 KB Output is correct
8 Correct 1350 ms 27536 KB Output is correct
9 Correct 811 ms 27784 KB Output is correct
10 Correct 424 ms 27784 KB Output is correct
11 Correct 1764 ms 27784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27784 KB Output is correct
2 Correct 1880 ms 150460 KB Output is correct
3 Correct 2067 ms 153500 KB Output is correct
4 Correct 1850 ms 153500 KB Output is correct
5 Correct 2281 ms 179740 KB Output is correct
6 Correct 2063 ms 179740 KB Output is correct
7 Correct 1840 ms 179740 KB Output is correct
8 Correct 1606 ms 179740 KB Output is correct
9 Correct 1512 ms 179740 KB Output is correct
10 Correct 1668 ms 179740 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16504 KB Output is correct
2 Correct 657 ms 25644 KB Output is correct
3 Correct 1663 ms 25792 KB Output is correct
4 Correct 1407 ms 25804 KB Output is correct
5 Correct 660 ms 26068 KB Output is correct
6 Correct 417 ms 26068 KB Output is correct
7 Correct 1736 ms 27536 KB Output is correct
8 Correct 1350 ms 27536 KB Output is correct
9 Correct 811 ms 27784 KB Output is correct
10 Correct 424 ms 27784 KB Output is correct
11 Correct 1764 ms 27784 KB Output is correct
12 Correct 21 ms 27784 KB Output is correct
13 Correct 1880 ms 150460 KB Output is correct
14 Correct 2067 ms 153500 KB Output is correct
15 Correct 1850 ms 153500 KB Output is correct
16 Correct 2281 ms 179740 KB Output is correct
17 Correct 2063 ms 179740 KB Output is correct
18 Correct 1840 ms 179740 KB Output is correct
19 Correct 1606 ms 179740 KB Output is correct
20 Correct 1512 ms 179740 KB Output is correct
21 Correct 1668 ms 179740 KB Output is correct
22 Execution timed out 8045 ms 209312 KB Time limit exceeded
23 Halted 0 ms 0 KB -