제출 #1361707

#제출 시각아이디문제언어결과실행 시간메모리
1361707orucRoadside Advertisements (NOI17_roadsideadverts)C++20
100 / 100
34 ms22684 KiB
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define endl '\n'

const int INF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7, LOG = 20, N = 2e5+5;

vector<vector<pair<int,int>>> g;
vector<int> in, dis, depth;
int tmr = 0;
vector<vector<int>> up(LOG+1, vector<int>(N+1));

void dfs(int v, int p){
    in[v] = ++tmr;
    up[0][v] = p;
    for(auto [u, d] : g[v]){
        if(u == p) continue;
        dis[u] = dis[v] + d;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
}

bool comp(const int &a, const int &b){
    return in[a] < in[b];
}

int LCA(int u, int v){
    if(depth[u] < depth[v]) swap(u,v);
    int s = depth[u] - depth[v];
    for(int i = LOG; i >= 0; i--){
        if(s & (1 << i)){
            u = up[i][u];
        }
    }
    if(u == v) return u;
    for(int i = LOG; i >= 0; i--){
        if(up[i][u] != up[i][v]){
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
}

int d(int u, int v){
    return dis[u] + dis[v] - 2*dis[LCA(u, v)];
}

void solve(){
    int n; cin >> n;
    g.assign(n+1, {});
    dis.resize(n+1);
    depth.resize(n+1);
    in.resize(n+1);
    for(int i = 2; i <= n; i++){
        int u,v,w; cin >> u >> v >> w;
        u++, v++;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1, 0);
    for(int j = 1; j <= LOG; j++){
        for(int i = 1; i <= n; i++){
            up[j][i] = up[j-1][up[j-1][i]];
        }
    }
    int q; cin >> q;
    while(q--){
        vector<int> v(5);
        for(int &i : v) cin >> i, i++;
        sort(v.begin(), v.end(), comp);
        cout << (d(v[0],v[1]) + d(v[1],v[2]) + d(v[2],v[3]) + d(v[3],v[4]) + d(v[4],v[0])) / 2 << endl;
    }
}


signed main(){  
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
}          

컴파일 시 표준 에러 (stderr) 메시지

roadsideadverts.cpp:6:17: warning: overflow in conversion from 'long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
    6 | const int INF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7, LOG = 20, N = 2e5+5;
      |                 ^~~~~~~~~~~~~~~~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…