oj.uz

답안 #253267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253267 2020-07-27T14:50:05 Z Autoratch 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 99828 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]) 
    {
        if(!t) rev.push_back(u);
        long long re = dist(u,x);
        if(!t) res[u][t] = min(res[u][t],re);
        else if(res[u][0]!=LLONG_MAX) ans = min(ans,res[u][0]+re);
    }
}

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] = 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 46 ms 12672 KB Output is correct
2 Correct 2130 ms 21396 KB Output is correct
3 Correct 3626 ms 21260 KB Output is correct
4 Correct 3484 ms 21620 KB Output is correct
5 Correct 3896 ms 21740 KB Output is correct
6 Correct 859 ms 21112 KB Output is correct
7 Correct 3582 ms 21424 KB Output is correct
8 Correct 3716 ms 21372 KB Output is correct
9 Correct 3821 ms 21624 KB Output is correct
10 Correct 881 ms 21112 KB Output is correct
11 Correct 3539 ms 21500 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12416 KB Output is correct
2 Correct 7975 ms 99100 KB Output is correct
3 Execution timed out 8038 ms 99828 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 12672 KB Output is correct
2 Correct 2130 ms 21396 KB Output is correct
3 Correct 3626 ms 21260 KB Output is correct
4 Correct 3484 ms 21620 KB Output is correct
5 Correct 3896 ms 21740 KB Output is correct
6 Correct 859 ms 21112 KB Output is correct
7 Correct 3582 ms 21424 KB Output is correct
8 Correct 3716 ms 21372 KB Output is correct
9 Correct 3821 ms 21624 KB Output is correct
10 Correct 881 ms 21112 KB Output is correct
11 Correct 3539 ms 21500 KB Output is correct
12 Correct 13 ms 12416 KB Output is correct
13 Correct 7975 ms 99100 KB Output is correct
14 Execution timed out 8038 ms 99828 KB Time limit exceeded
15 Halted 0 ms 0 KB -