제출 #77864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77864		thebes	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	489 ms	105148 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MN = 1e5+5;
int dp[MN][2], sp[MN][20][2], anc[MN][20], N, M, i, x, y, w, dep[MN];
struct qur{int x, y, w;}path[MN];
vector<int> adj[MN], id[MN];
vector<pair<int,int>> bld[MN];
void init(int n,int p,int d){
    dep[n]=d; anc[n][0]=p;
    for(auto v : adj[n])
        if(v != p) init(v, n, d+1);
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[x]-dep[y]>=(1<<i))
            x = anc[x][i];
    }
    if(x == y) return x;
    for(int i=19;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}
int qu(int x,int y,int id){
    int res = 0;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[x]-dep[y]>=(1<<i))
            res += sp[x][i][id], x = anc[x][i];
    }
    if(x == y) return res;
    for(int i=19;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            res += sp[x][i][id]+sp[y][i][id];
            x = anc[x][i], y = anc[y][i];
        }
    }
    return res+sp[x][0][id]+sp[y][0][id]+dp[anc[x][0]][id];
}
int adv(int n,int d){
    for(int i=19;i>=0;i--){
        if((1<<i)<=d)
            n=anc[n][i],d-=(1<<i);
    }
    return n;
}
void solve(int n,int p){
    for(int i=1;i<20;i++)
        bld[adv(n,(1<<i)-1)].push_back({n,i});
    for(auto v : adj[n]){
        if(v == p) continue;
        solve(v, n);
        dp[n][1] += dp[v][0];
    }
    dp[n][0]=dp[n][1];
    for(auto i : id[n]){
        int x = path[i].x, y = path[i].y, w = path[i].w;
        dp[n][0]=max(dp[n][0],qu(x,y,1)-qu(x,y,0)+dp[n][0]+w);
    }
    sp[n][0][0]=dp[n][0];
    sp[n][0][1]=dp[n][1];
    sort(bld[n].begin(),bld[n].end(),[](pair<int,int>i,pair<int,int>j){return dep[i.first]<dep[j.first];});
    for(auto v : bld[n]){
        for(int i=0;i<2;i++)
            sp[v.first][v.second][i]=sp[v.first][v.second-1][i]+sp[anc[v.first][v.second-1]][v.second-1][i];
    }
}
signed main(){
    for(scanf("%lld",&N),i=1;i<N;i++){
        scanf("%lld%lld",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    init(1, 0, 1);
    for(int j=1;j<20;j++){
        for(i=1;i<=N;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1];
    }
    for(scanf("%lld",&M),i=1;i<=M;i++){
        scanf("%lld%lld%lld",&x,&y,&w);
        path[i] = {x, y, w};
        id[lca(x,y)].push_back(i);
    }
    solve(1, 0);
    printf("%lld\n",dp[1][0]);
    return 0;
}

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

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:75:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&N),i=1;i<N;i++){
         ~~~~~~~~~~~~~~~~^~~~
election_campaign.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~
election_campaign.cpp:85:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&M),i=1;i<=M;i++){
         ~~~~~~~~~~~~~~~~^~~~
election_campaign.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&x,&y,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40