oj.uz

답안 #253264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253264 2020-07-27T14:43:41 Z Autoratch 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 97872 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 48 ms 12672 KB Output is correct
2 Correct 2241 ms 21652 KB Output is correct
3 Correct 3835 ms 21500 KB Output is correct
4 Correct 3696 ms 21756 KB Output is correct
5 Correct 4176 ms 21732 KB Output is correct
6 Correct 892 ms 21132 KB Output is correct
7 Correct 3803 ms 21392 KB Output is correct
8 Correct 3952 ms 21760 KB Output is correct
9 Correct 4161 ms 21752 KB Output is correct
10 Correct 907 ms 21156 KB Output is correct
11 Correct 3736 ms 21296 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 12672 KB Output is correct
2 Correct 2241 ms 21652 KB Output is correct
3 Correct 3835 ms 21500 KB Output is correct
4 Correct 3696 ms 21756 KB Output is correct
5 Correct 4176 ms 21732 KB Output is correct
6 Correct 892 ms 21132 KB Output is correct
7 Correct 3803 ms 21392 KB Output is correct
8 Correct 3952 ms 21760 KB Output is correct
9 Correct 4161 ms 21752 KB Output is correct
10 Correct 907 ms 21156 KB Output is correct
11 Correct 3736 ms 21296 KB Output is correct
12 Correct 12 ms 12416 KB Output is correct
13 Execution timed out 8071 ms 97872 KB Time limit exceeded
14 Halted 0 ms 0 KB -