oj.uz

Submission #270367

# Submission time Handle Problem Language Result Execution time Memory
270367 2020-08-17T14:25:03 Z Autoratch Factories (JOI14_factories) C++14
33 / 100
 8000 ms 424412 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];
vector<pair<long long,int> > diss[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,int st,long long w)
{ 
    sz[u] = 1; 
    if(st!=-1) diss[u].push_back({w,st}); 
    for(auto [d,v] : adj[u]) if(v!=p and !blocked[v]) getsz(v,u,st,w+d),sz[u]+=sz[v]; 
}
 
void build(int u,int cp)
{
    getsz(u,cp,-1,0);
    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;
    }
    getsz(c,c,c,0);
    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);
    }
}
 
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)
{
    for(auto [d,u] : diss[x])
    {
        rev.push_back(u);
        res[u][t] = min(res[u][t],d);
        if(res[u][0]!=LLONG_MAX and res[u][1]!=LLONG_MAX) ans = min(ans,res[u][0]+res[u][1]);
    }
    /*
    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:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     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, int, long long int)':
factories.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [d,v] : adj[u]) if(v!=p and !blocked[v]) getsz(v,u,st,w+d),sz[u]+=sz[v];
      |              ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto [d,v] : adj[c]) if(v!=prev and !blocked[v] and sz[v]>mx) mx = sz[v],r = v;
      |                  ^
factories.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
      |              ^
factories.cpp: In function 'void upd(int, int)':
factories.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto [d,u] : diss[x])
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24448 KB Output is correct
2 Correct 520 ms 33788 KB Output is correct
3 Correct 601 ms 34072 KB Output is correct
4 Correct 580 ms 43780 KB Output is correct
5 Correct 642 ms 44408 KB Output is correct
6 Correct 584 ms 42616 KB Output is correct
7 Correct 579 ms 43512 KB Output is correct
8 Correct 634 ms 43976 KB Output is correct
9 Correct 626 ms 44408 KB Output is correct
10 Correct 387 ms 42616 KB Output is correct
11 Correct 613 ms 43488 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24224 KB Output is correct
2 Correct 3345 ms 237868 KB Output is correct
3 Correct 4776 ms 309724 KB Output is correct
4 Correct 1277 ms 153176 KB Output is correct
5 Correct 6579 ms 418664 KB Output is correct
6 Correct 5091 ms 328728 KB Output is correct
7 Correct 1907 ms 91836 KB Output is correct
8 Correct 872 ms 69276 KB Output is correct
9 Correct 1822 ms 106196 KB Output is correct
10 Correct 1883 ms 93176 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24448 KB Output is correct
2 Correct 520 ms 33788 KB Output is correct
3 Correct 601 ms 34072 KB Output is correct
4 Correct 580 ms 43780 KB Output is correct
5 Correct 642 ms 44408 KB Output is correct
6 Correct 584 ms 42616 KB Output is correct
7 Correct 579 ms 43512 KB Output is correct
8 Correct 634 ms 43976 KB Output is correct
9 Correct 626 ms 44408 KB Output is correct
10 Correct 387 ms 42616 KB Output is correct
11 Correct 613 ms 43488 KB Output is correct
12 Correct 22 ms 24224 KB Output is correct
13 Correct 3345 ms 237868 KB Output is correct
14 Correct 4776 ms 309724 KB Output is correct
15 Correct 1277 ms 153176 KB Output is correct
16 Correct 6579 ms 418664 KB Output is correct
17 Correct 5091 ms 328728 KB Output is correct
18 Correct 1907 ms 91836 KB Output is correct
19 Correct 872 ms 69276 KB Output is correct
20 Correct 1822 ms 106196 KB Output is correct
21 Correct 1883 ms 93176 KB Output is correct
22 Correct 5030 ms 265604 KB Output is correct
23 Correct 4000 ms 270516 KB Output is correct
24 Correct 5829 ms 342728 KB Output is correct
25 Correct 7373 ms 345372 KB Output is correct
26 Correct 7059 ms 336208 KB Output is correct
27 Execution timed out 8138 ms 424412 KB Time limit exceeded
28 Halted 0 ms 0 KB -