oj.uz

답안 #253247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253247 2020-07-27T14:22:43 Z Autoratch 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 117532 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);
        res[u][t] = min(res[u][t],dist(u,x));
        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 47 ms 12800 KB Output is correct
2 Correct 2133 ms 21624 KB Output is correct
3 Correct 3769 ms 21616 KB Output is correct
4 Correct 3647 ms 31260 KB Output is correct
5 Correct 4128 ms 31408 KB Output is correct
6 Correct 939 ms 30748 KB Output is correct
7 Correct 3593 ms 30716 KB Output is correct
8 Correct 3851 ms 30936 KB Output is correct
9 Correct 4136 ms 31200 KB Output is correct
10 Correct 906 ms 30840 KB Output is correct
11 Correct 3653 ms 30848 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12544 KB Output is correct
2 Correct 7553 ms 99120 KB Output is correct
3 Execution timed out 8089 ms 117532 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 12800 KB Output is correct
2 Correct 2133 ms 21624 KB Output is correct
3 Correct 3769 ms 21616 KB Output is correct
4 Correct 3647 ms 31260 KB Output is correct
5 Correct 4128 ms 31408 KB Output is correct
6 Correct 939 ms 30748 KB Output is correct
7 Correct 3593 ms 30716 KB Output is correct
8 Correct 3851 ms 30936 KB Output is correct
9 Correct 4136 ms 31200 KB Output is correct
10 Correct 906 ms 30840 KB Output is correct
11 Correct 3653 ms 30848 KB Output is correct
12 Correct 12 ms 12544 KB Output is correct
13 Correct 7553 ms 99120 KB Output is correct
14 Execution timed out 8089 ms 117532 KB Time limit exceeded
15 Halted 0 ms 0 KB -