oj.uz

답안 #268196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268196 2020-08-16T10:23:01 Z Autoratch 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 154820 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],lcc[N][K];
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 cn)
{
    int l;
    if(lcc[a][cn]) l = lcc[a][cn];
    else l = lcc[a][cn] = lca(a,b);
    return dis[a]+dis[b]-dis[l]-dis[l]; 
}
 
void upd(int t,int x)
{
    int cnt = 0;
    for(int u = x;u;u = pa[u]) 
    {
        rev.push_back(u); 
        res[u][t] = min(res[u][t],dist(x,u,cnt));
        if(res[u][0]!=LLONG_MAX and res[u][1]!=LLONG_MAX) ans = min(ans,res[u][0]+res[u][1]);
        cnt++;
    }
}
 
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: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     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: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 | 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: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         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: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
      |              ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 12672 KB Output is correct
2 Correct 472 ms 31116 KB Output is correct
3 Correct 540 ms 31224 KB Output is correct
4 Correct 579 ms 31480 KB Output is correct
5 Correct 619 ms 31524 KB Output is correct
6 Correct 336 ms 31096 KB Output is correct
7 Correct 532 ms 30968 KB Output is correct
8 Correct 537 ms 31224 KB Output is correct
9 Correct 637 ms 31480 KB Output is correct
10 Correct 328 ms 30968 KB Output is correct
11 Correct 538 ms 31096 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 12544 KB Output is correct
2 Correct 4981 ms 154820 KB Output is correct
3 Execution timed out 8105 ms 154752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 12672 KB Output is correct
2 Correct 472 ms 31116 KB Output is correct
3 Correct 540 ms 31224 KB Output is correct
4 Correct 579 ms 31480 KB Output is correct
5 Correct 619 ms 31524 KB Output is correct
6 Correct 336 ms 31096 KB Output is correct
7 Correct 532 ms 30968 KB Output is correct
8 Correct 537 ms 31224 KB Output is correct
9 Correct 637 ms 31480 KB Output is correct
10 Correct 328 ms 30968 KB Output is correct
11 Correct 538 ms 31096 KB Output is correct
12 Correct 10 ms 12544 KB Output is correct
13 Correct 4981 ms 154820 KB Output is correct
14 Execution timed out 8105 ms 154752 KB Time limit exceeded
15 Halted 0 ms 0 KB -