oj.uz

답안 #253263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253263 2020-07-27T14:40:44 Z Autoratch 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 99224 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];
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);
}

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;
}

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 l = lca(a,b);  
    return dis[a]+dis[b]-dis[l]-dis[l]; 
}

void upd(int t,int x)
{
    for(int u = x;u;u = pa[u]) 
    {
        rev.push_back(u);
        long long re = dist(u,x);
        if(re<res[u][t]) res[u][t] = re;
        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: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     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: decomposition declaration only available with -std=c++1z or -std=gnu++1z
 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:21:50: warning: unused variable 'd' [-Wunused-variable]
 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: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [d,v] : adj[c]) if(v!=prev and !blocked[v] and sz[v]>mx) mx = sz[v],r = v;
                  ^
factories.cpp:30:22: warning: unused variable 'd' [-Wunused-variable]
         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: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
              ^
factories.cpp:35:18: warning: unused variable 'd' [-Wunused-variable]
     for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
                  ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 12672 KB Output is correct
2 Correct 2187 ms 21924 KB Output is correct
3 Correct 3753 ms 21908 KB Output is correct
4 Correct 3627 ms 22064 KB Output is correct
5 Correct 4314 ms 22264 KB Output is correct
6 Correct 883 ms 21624 KB Output is correct
7 Correct 3717 ms 21540 KB Output is correct
8 Correct 4006 ms 21820 KB Output is correct
9 Correct 4148 ms 22008 KB Output is correct
10 Correct 912 ms 21512 KB Output is correct
11 Correct 3675 ms 21696 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Execution timed out 8023 ms 99224 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 12672 KB Output is correct
2 Correct 2187 ms 21924 KB Output is correct
3 Correct 3753 ms 21908 KB Output is correct
4 Correct 3627 ms 22064 KB Output is correct
5 Correct 4314 ms 22264 KB Output is correct
6 Correct 883 ms 21624 KB Output is correct
7 Correct 3717 ms 21540 KB Output is correct
8 Correct 4006 ms 21820 KB Output is correct
9 Correct 4148 ms 22008 KB Output is correct
10 Correct 912 ms 21512 KB Output is correct
11 Correct 3675 ms 21696 KB Output is correct
12 Correct 12 ms 12416 KB Output is correct
13 Execution timed out 8023 ms 99224 KB Time limit exceeded
14 Halted 0 ms 0 KB -