oj.uz

답안 #253269

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

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 41 ms 12672 KB Output is correct
2 Correct 1948 ms 21140 KB Output is correct
3 Correct 3323 ms 21380 KB Output is correct
4 Correct 2611 ms 21520 KB Output is correct
5 Correct 3613 ms 21656 KB Output is correct
6 Correct 779 ms 21112 KB Output is correct
7 Correct 3241 ms 21500 KB Output is correct
8 Correct 3426 ms 21452 KB Output is correct
9 Correct 3755 ms 21628 KB Output is correct
10 Correct 807 ms 21276 KB Output is correct
11 Correct 3211 ms 21412 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 12672 KB Output is correct
2 Correct 1948 ms 21140 KB Output is correct
3 Correct 3323 ms 21380 KB Output is correct
4 Correct 2611 ms 21520 KB Output is correct
5 Correct 3613 ms 21656 KB Output is correct
6 Correct 779 ms 21112 KB Output is correct
7 Correct 3241 ms 21500 KB Output is correct
8 Correct 3426 ms 21452 KB Output is correct
9 Correct 3755 ms 21628 KB Output is correct
10 Correct 807 ms 21276 KB Output is correct
11 Correct 3211 ms 21412 KB Output is correct
12 Correct 12 ms 12416 KB Output is correct
13 Correct 7309 ms 99084 KB Output is correct
14 Execution timed out 8031 ms 100060 KB Time limit exceeded
15 Halted 0 ms 0 KB -