oj.uz

Submission #364654

# Submission time Handle Problem Language Result Execution time Memory
364654 2021-02-09T16:35:18 Z bigDuck Factories (JOI14_factories) C++14
33 / 100
 8000 ms 116820 KB 
#include "factories.h"

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

int anc[500010][21];



vector<pii> g[500010];
ll d[500010];

int tmp=0;
int ent[500010], ex[500010];


int n;
void dfs(int s){
tmp++;
ent[s]=tmp;
for(pii pr:g[s]){
    int u=pr.ft, c=pr.sc;
    if(u==anc[s][0]){continue;}
    d[u]=d[s]+c;
    anc[u][0]=s;
    dfs(u);
}
tmp++;
ex[s]=tmp;
return;
}


void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0; i<(n-1); i++){
        g[A[i]+1 ].pb({B[i]+1, D[i]});
        g[B[i]+1 ].pb({A[i]+1, D[i]});
    }
    dfs(1);
    for(int i=1; i<=20; i++){
        for(int j=1; j<=n; j++){
            anc[j][i]=anc[anc[j][i-1] ][i-1];
        }
    }
    return;
}


bool is_anc(int u, int v){
    return (ent[u]<=ent[v]) && (ex[u]>=ex[v]);
}



int lca(int u, int v){
if( is_anc(u, v) ){
    return u;
}
int cr=u;

for(int i=20; i>=0; i--){
    if( (anc[cr][i]!=(0)) && (!is_anc(anc[cr][i], v)) ){
        cr=anc[cr][i];
    }
}
return anc[cr][0];
}


bool v[500010];
int mrk[5010];
ll d1[5010];

ll dfs0(int s){
ll res=1e18;
//cout<<"x"<<flush;

if(mrk[s]==1){
    d1[s]=0;
}
else{
        if(d1[s]==0){
    d1[s]=1e18;}
}
//cout<<s<<" "<<mrk[s]<<" "<<d1[s]<<"\n";
v[s]=true;
for(pii pr:g[s]){
    int u=pr.ft, c=pr.sc;
    if(v[u]){continue;}
    d1[u]=min(d1[s]+c, d1[u]);
    res=min(res, dfs0(u));
    d1[s]=min(d1[u]+c, d1[s]);
}
v[s]=false;




if(mrk[s]==2){
    res=min(res, d1[s]);
}
//return res;
return res;
}

long long Query(int S, int X[], int T, int Y[]) {
  ll res=1e18;

  if( n<=5000 ){
    for(int i=0; i<S; i++){
        mrk[X[i]+1 ]=1;
    }
    //ll res=1e18;
    for(int i=0; i<T; i++){
        mrk[Y[i]+1 ]=2;
    }
    //res=min(res, (dfs0(1)).ft);
    ll r=dfs0(1);
    r=dfs0(1);
    res=min(res, r);
    for(int i=0; i<S; i++){
        mrk[X[i]+1 ]=0;
    }
    //ll res=1e18;
    for(int i=0; i<T; i++){
        mrk[Y[i]+1 ]=0;
    }
    for(int i=1;i<=n; i++){
        d1[i]=0;
    }
  }
  else{


  for(int i=0; i<S; i++){
    for(int j=0; j<T; j++){
        int u=X[i]+1, v=Y[j]+1;
        int anc=lca(u, v);
        res=min(res, d[u]+d[v]-2*d[anc]);
    }
  }
  }
  return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12396 KB Output is correct
2 Correct 1822 ms 24256 KB Output is correct
3 Correct 2029 ms 26328 KB Output is correct
4 Correct 1958 ms 26380 KB Output is correct
5 Correct 2068 ms 26612 KB Output is correct
6 Correct 963 ms 26220 KB Output is correct
7 Correct 2000 ms 26036 KB Output is correct
8 Correct 1981 ms 26220 KB Output is correct
9 Correct 2111 ms 26348 KB Output is correct
10 Correct 985 ms 26092 KB Output is correct
11 Correct 2023 ms 26236 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12268 KB Output is correct
2 Correct 1281 ms 92612 KB Output is correct
3 Correct 4403 ms 94272 KB Output is correct
4 Correct 937 ms 93268 KB Output is correct
5 Correct 3378 ms 116820 KB Output is correct
6 Correct 3345 ms 95488 KB Output is correct
7 Correct 5384 ms 36608 KB Output is correct
8 Correct 915 ms 37344 KB Output is correct
9 Correct 3557 ms 40240 KB Output is correct
10 Correct 3142 ms 38004 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12396 KB Output is correct
2 Correct 1822 ms 24256 KB Output is correct
3 Correct 2029 ms 26328 KB Output is correct
4 Correct 1958 ms 26380 KB Output is correct
5 Correct 2068 ms 26612 KB Output is correct
6 Correct 963 ms 26220 KB Output is correct
7 Correct 2000 ms 26036 KB Output is correct
8 Correct 1981 ms 26220 KB Output is correct
9 Correct 2111 ms 26348 KB Output is correct
10 Correct 985 ms 26092 KB Output is correct
11 Correct 2023 ms 26236 KB Output is correct
12 Correct 19 ms 12268 KB Output is correct
13 Correct 1281 ms 92612 KB Output is correct
14 Correct 4403 ms 94272 KB Output is correct
15 Correct 937 ms 93268 KB Output is correct
16 Correct 3378 ms 116820 KB Output is correct
17 Correct 3345 ms 95488 KB Output is correct
18 Correct 5384 ms 36608 KB Output is correct
19 Correct 915 ms 37344 KB Output is correct
20 Correct 3557 ms 40240 KB Output is correct
21 Correct 3142 ms 38004 KB Output is correct
22 Execution timed out 8071 ms 97332 KB Time limit exceeded
23 Halted 0 ms 0 KB -