답안 #959510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959510 2024-04-08T11:08:53 Z dong_gas 공장들 (JOI14_factories) C++17
컴파일 오류
0 ms 0 KB
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, q;
int sz[500050], use[500050], cent_papa[500050], papa[500050][23], dep[500050];
ll dp[500050];
vector<pint> adj[500050];
ll m[500050];

void dfs(int u, int p=0) {
    papa[u][0]=p;
    dep[u]=dep[p]+1;
    for(auto& [v, w]: adj[u]) {
        if(v==p) continue;
        dp[v]=dp[u]+w;
        dfs(v,u);
    }
}

int lca(int u, int v) {
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=22;i>=0;i--) if(dep[u]-dep[v]>=(1<<i)) u=papa[u][i];
    if(u==v) return u;
    for(int i=22;i>=0;i--) if(papa[u][i] ^ papa[v][i]) u=papa[u][i], v=papa[v][i];
    return papa[u][0];
}

ll get_dist(int u, int v) { return dp[u]+dp[v]-2*dp[lca(u,v)]; }

int get_size(int u, int p=0) {
    sz[u]=1;
    for(auto& [v, w]:adj[u]) {
        if(use[v] || p==v) continue;
        sz[u]+=get_size(v,u);
    }
    return sz[u];
}

int get_cent(int u, int p, int cnt) {
    for(auto& [v, w]:adj[u]) {
        if(use[v] || v==p) continue;
        if(sz[v]>cnt/2) return get_cent(v,u,cnt);
    }
    return u;
}

void dnc(int u, int p=0) {//p는 이전 cent
    int cent=get_cent(u,p,get_size(u,p));
    cent_papa[cent]=p;
    use[cent]=1;
    for(auto& [v, w]:adj[cent]) if(!use[v]) dnc(v,cent);
}

void update(int u) {
    int now=u;
    do {
        ll dist=get_dist(now,u);
        m[now]=min(m[now],dist);
        now=cent_papa[now];
    } while(now!=0);    
}

void downdate(int u) {
    int now=u;
    do {
        ll dist=get_dist(now,u);
        m[now]=1e18;
        now=cent_papa[now];
    } while(now!=0);    
}

ll query(int u) {
    int now=u;
    ll ret=1e18;
    do {        
        ret=min(ret, get_dist(u,now) + m[now]);
        now=cent_papa[now];        
    } while(now!=0);
    return (ret<1e18) ? ret : -1;
}

void Init(int N, vector<int> A, vector<int> B, vector<int> D) {
    n=N;
    for(int i=0;i<n-1;i++) {
        adj[A[i]+1].emplace_back(B[i]+1,D[i]);
        adj[B[i]+1].emplace_back(A[i]+1,D[i]);
    }
    dfs(1), dnc(1);
    fill(m+1,m+n+1,1e18);
    for(int j=1;j<23;j++) for(int i=1;i<=n;i++) papa[i][j]=papa[papa[i][j-1]][j-1];
}

ll Query(int S, vector<int> X, int T, vector<int> Y) {
    ll ret=1e18;
    for(int& x:X) update(x+1);
    for(int& y:Y) ret=min(ret,query(y+1));
    for(int& x:X) downdate(x+1);
    return ret;
}

Compilation message

factories.cpp: In function 'void downdate(int)':
factories.cpp:73:12: warning: unused variable 'dist' [-Wunused-variable]
   73 |         ll dist=get_dist(now,u);
      |            ^~~~
/usr/bin/ld: /tmp/ccMPcpyV.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status