oj.uz

답안 #270377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
270377 2020-08-17T14:30:24 Z Autoratch 공장들 (JOI14_factories) C++14
100 / 100
 6893 ms 399868 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];
vector<pair<long long,int> > diss[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,int st,long long w)
{ 
    sz[u] = 1; 
    if(st!=-1) diss[u].push_back({w,st}); 
    for(auto [d,v] : adj[u]) if(v!=p and !blocked[v]) getsz(v,u,st,w+d),sz[u]+=sz[v]; 
}
 
void build(int u,int cp)
{
    getsz(u,cp,-1,0);
    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;
    }
    getsz(c,c,c,0);
    pa[c] = cp,blocked[c] = true;
    for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
}
  
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];
}

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] = 1e18;
}
 
long long dist(int a,int b,int cn)
{
    int l = lcc[a][cn];
    return dis[a]+dis[b]-dis[l]-dis[l]; 
}
 
void upd(int t,int x)
{
    for(auto [d,u] : diss[x])
    {
        rev.push_back(u);
        res[u][t] = min(res[u][t],d);
    }
    /*
    for(int u = x,cnt = 0;u;u = pa[u],cnt++) 
    {
        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]);
    }
    */
}
 
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) ans = min(ans,res[x][0]+res[x][1]),res[x][0] = res[x][1] = 1e18;
    rev.clear();
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     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, int, long long int)':
factories.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [d,v] : adj[u]) if(v!=p and !blocked[v]) getsz(v,u,st,w+d),sz[u]+=sz[v];
      |              ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto [d,v] : adj[c]) if(v!=prev and !blocked[v] and sz[v]>mx) mx = sz[v],r = v;
      |                  ^
factories.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [d,v] : adj[c]) if(!blocked[v]) build(v,c);
      |              ^
factories.cpp: In function 'void upd(int, int)':
factories.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for(auto [d,u] : diss[x])
      |              ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 24440 KB Output is correct
2 Correct 515 ms 33912 KB Output is correct
3 Correct 622 ms 34012 KB Output is correct
4 Correct 558 ms 34296 KB Output is correct
5 Correct 609 ms 34940 KB Output is correct
6 Correct 409 ms 33144 KB Output is correct
7 Correct 579 ms 34060 KB Output is correct
8 Correct 596 ms 34424 KB Output is correct
9 Correct 617 ms 34992 KB Output is correct
10 Correct 372 ms 33144 KB Output is correct
11 Correct 555 ms 34040 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 3166 ms 237764 KB Output is correct
3 Correct 4687 ms 309848 KB Output is correct
4 Correct 1338 ms 134876 KB Output is correct
5 Correct 5723 ms 399868 KB Output is correct
6 Correct 4692 ms 310044 KB Output is correct
7 Correct 1572 ms 77816 KB Output is correct
8 Correct 750 ms 55176 KB Output is correct
9 Correct 1761 ms 92080 KB Output is correct
10 Correct 1585 ms 79080 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 24440 KB Output is correct
2 Correct 515 ms 33912 KB Output is correct
3 Correct 622 ms 34012 KB Output is correct
4 Correct 558 ms 34296 KB Output is correct
5 Correct 609 ms 34940 KB Output is correct
6 Correct 409 ms 33144 KB Output is correct
7 Correct 579 ms 34060 KB Output is correct
8 Correct 596 ms 34424 KB Output is correct
9 Correct 617 ms 34992 KB Output is correct
10 Correct 372 ms 33144 KB Output is correct
11 Correct 555 ms 34040 KB Output is correct
12 Correct 19 ms 24192 KB Output is correct
13 Correct 3166 ms 237764 KB Output is correct
14 Correct 4687 ms 309848 KB Output is correct
15 Correct 1338 ms 134876 KB Output is correct
16 Correct 5723 ms 399868 KB Output is correct
17 Correct 4692 ms 310044 KB Output is correct
18 Correct 1572 ms 77816 KB Output is correct
19 Correct 750 ms 55176 KB Output is correct
20 Correct 1761 ms 92080 KB Output is correct
21 Correct 1585 ms 79080 KB Output is correct
22 Correct 3704 ms 241424 KB Output is correct
23 Correct 4057 ms 245780 KB Output is correct
24 Correct 5792 ms 318388 KB Output is correct
25 Correct 5829 ms 320756 KB Output is correct
26 Correct 5800 ms 312028 KB Output is correct
27 Correct 6893 ms 399716 KB Output is correct
28 Correct 1741 ms 165468 KB Output is correct
29 Correct 5451 ms 335080 KB Output is correct
30 Correct 5368 ms 334216 KB Output is correct
31 Correct 5288 ms 335064 KB Output is correct
32 Correct 1761 ms 113424 KB Output is correct
33 Correct 834 ms 70580 KB Output is correct
34 Correct 1397 ms 84216 KB Output is correct
35 Correct 1374 ms 84856 KB Output is correct
36 Correct 1838 ms 90160 KB Output is correct
37 Correct 1545 ms 90016 KB Output is correct