oj.uz

Submission #268671

# Submission time Handle Problem Language Result Execution time Memory
268671 2020-08-16T17:02:38 Z Autoratch Factories (JOI14_factories) C++14
15 / 100
 8000 ms 143936 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 1;
const int K = 19;
 
vector<pair<int,int> > adj[N];
int sz[N],lv[N],dp[K][N],pa[N],lcc[N][K];
long long dis[N];
bool blocked[N];
long long res[N][2],ans;
vector<int> rev;
 
void dfs(int u,int p)
{
    dp[0][u] = p,lv[u] = lv[p]+1;
    for(auto [d,v] : adj[u]) if(v!=p) dis[v] = dis[u]+d,dfs(v,u);
}
 
void getsz(int u,int p){ sz[u] = 1; for(auto [d,v] : adj[u]) if(v!=p and !blocked[v]) getsz(v,u),sz[u]+=sz[v]; }
 
void build(int u,int cp)
{
    getsz(u,cp);
    int c = u,prev = 0;
    while(true)
    {
        int mx = -1,r = 0;
        for(auto [d,v] : adj[c]) if(v!=prev and !blocked[v] and sz[v]>mx) mx = sz[v],r = v;
        if(mx*2>sz[u]) prev = c,c = r;
        else break;
    }
    pa[c] = cp,blocked[c] = true;
    for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
}
  
int lca(int a,int b)
{
    if(lv[a]<lv[b]) swap(a,b);
    for(int i = K-1;i >= 0;i--) if(lv[dp[i][a]]>=lv[b]) a = dp[i][a];
    if(a==b) return a;
    for(int i = K-1;i >= 0;i--) if(dp[i][a]!=dp[i][b]) a = dp[i][a],b = dp[i][b];
    return dp[0][a];
}

void Init(int n,int a[],int b[],int d[]) 
{
    for(int i = 0;i < n-1;i++) a[i]++,b[i]++;
    for(int i = 0;i < n-1;i++)
    {
        adj[a[i]].push_back({d[i],b[i]});
        adj[b[i]].push_back({d[i],a[i]});
    }
    dfs(1,0);
    build(1,0);
    for(int i = 1;i < K;i++) for(int j = 1;j <= n;j++) dp[i][j] = dp[i-1][dp[i-1][j]];
    for(int i = 1;i <= n;i++) res[i][0] = res[i][1] = LLONG_MAX;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 0,x = i;x;x = pa[x],j++) lcc[i][j] = lca(i,x);
    }
}
 
/*int lca(int a,int b)
{
    if(lv[a]<lv[b]) swap(a,b);
    for(int i = K-1;i >= 0;i--) if(lv[dp[i][a]]>=lv[b]) a = dp[i][a];
    if(a==b) return a;
    for(int i = K-1;i >= 0;i--) if(dp[i][a]!=dp[i][b]) a = dp[i][a],b = dp[i][b];
    return dp[0][a];
}*/
 
long long dist(int a,int b,int cn)
{
    int l = lcc[a][cn];
    return dis[a]+dis[b]-dis[l]-dis[l]; 
}
 
void upd(int t,int x)
{
    int cnt = 0;
    for(int u = x,cnt = 0;u;u = pa[u],cnt++) 
    {
        rev.push_back(u); 
        res[u][t] = min(res[u][t],dist(x,u,cnt));
        if(res[u][0]!=LLONG_MAX and res[u][1]!=LLONG_MAX) ans = min(ans,res[u][0]+res[u][1]);
    }
}
 
long long Query(int s,int x[],int t,int y[]) 
{
    for(int i = 0;i < s;i++) x[i]++;
    for(int i = 0;i < t;i++) y[i]++;
    ans = LLONG_MAX;
    for(int i = 0;i < s;i++) upd(0,x[i]);
    for(int i = 0;i < t;i++) upd(1,y[i]);
    for(int x : rev) res[x][0] = res[x][1] = LLONG_MAX;
    rev.clear();
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto [d,v] : adj[u]) if(v!=p) dis[v] = dis[u]+d,dfs(v,u);
      |              ^
factories.cpp: In function 'void getsz(int, int)':
factories.cpp:21:46: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 | void getsz(int u,int p){ sz[u] = 1; for(auto [d,v] : adj[u]) if(v!=p and !blocked[v]) getsz(v,u),sz[u]+=sz[v]; }
      |                                              ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:30:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         for(auto [d,v] : adj[c]) if(v!=prev and !blocked[v] and sz[v]>mx) mx = sz[v],r = v;
      |                  ^
factories.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
      |              ^
factories.cpp: In function 'void upd(int, int)':
factories.cpp:82:9: warning: unused variable 'cnt' [-Wunused-variable]
   82 |     int cnt = 0;
      |         ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12800 KB Output is correct
2 Correct 486 ms 31096 KB Output is correct
3 Correct 554 ms 30968 KB Output is correct
4 Correct 534 ms 31228 KB Output is correct
5 Correct 616 ms 31480 KB Output is correct
6 Correct 353 ms 31100 KB Output is correct
7 Correct 547 ms 30972 KB Output is correct
8 Correct 554 ms 31224 KB Output is correct
9 Correct 592 ms 31408 KB Output is correct
10 Correct 339 ms 30920 KB Output is correct
11 Correct 536 ms 30968 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12544 KB Output is correct
2 Correct 3607 ms 143936 KB Output is correct
3 Execution timed out 8101 ms 135392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12800 KB Output is correct
2 Correct 486 ms 31096 KB Output is correct
3 Correct 554 ms 30968 KB Output is correct
4 Correct 534 ms 31228 KB Output is correct
5 Correct 616 ms 31480 KB Output is correct
6 Correct 353 ms 31100 KB Output is correct
7 Correct 547 ms 30972 KB Output is correct
8 Correct 554 ms 31224 KB Output is correct
9 Correct 592 ms 31408 KB Output is correct
10 Correct 339 ms 30920 KB Output is correct
11 Correct 536 ms 30968 KB Output is correct
12 Correct 12 ms 12544 KB Output is correct
13 Correct 3607 ms 143936 KB Output is correct
14 Execution timed out 8101 ms 135392 KB Time limit exceeded
15 Halted 0 ms 0 KB -