제출 #295008

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

election_campaign

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

typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second

const int MN = 1e5+5;
int N, M, i, x, y, w, f[MN], g[MN], sz[MN], vis[MN][2], st[3*MN], lnk[MN], par[MN], nxt;
vi adj[MN]; pii big[MN];
struct plan{int x, y, w;};
vector<plan> vec[MN];

void dfs(int n,int p){
    vis[n][0] = ++nxt;
    par[n] = p; sz[n] = 1;
    big[n] = {-1, -1};
    for(auto v : adj[n]){
        if(v==p) continue;
        dfs(v, n);
        sz[n] += sz[v];
        if(sz[v]>big[n].F) big[n]={sz[v],v};
    }
    vis[n][1] = nxt;
    if(big[n].S!=-1) lnk[big[n].S]=n;
}

void dfs2(int n,int p){
    if(!lnk[n]) lnk[n] = n;
    else lnk[n] = lnk[lnk[n]];
    for(auto v : adj[n]){
        if(v==p) continue;
        dfs2(v, n);
    }
}

inline bool con(int x,int y){return vis[x][0]<=vis[y][0]&&vis[y][1]<=vis[x][1];}
inline int lca(int x,int y){
    while(!con(lnk[x],y)) x=par[lnk[x]];
    while(!con(lnk[y],x)) y=par[lnk[y]];
    return con(x,y)?x:y;
}

void upd(int i,int s,int e,int ss,int se,int val){
    if(s>=ss&&e<=se) st[i] += val;
    else if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,val);
    else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,val);
    else upd(2*i,s,(s+e)/2,ss,se,val), upd(2*i+1,(s+e)/2+1,e,ss,se,val);
}

int qu(int i,int s,int e,int idx){
    if(s^e){
        if((s+e)/2<idx) return st[i]+qu(2*i+1,(s+e)/2+1,e,idx);
        else return st[i]+qu(2*i,s,(s+e)/2,idx);
    }
    else return st[i];
}

void solve(int n,int p){
    for(auto v : adj[n]){
        if(v==p) continue;
        solve(v, n);
        g[n] += max(g[v],f[v]);
    }
    for(auto v : vec[n])
        f[n] = max(f[n],qu(1,1,N,vis[v.x][0])+qu(1,1,N,vis[v.y][0])+g[n]+v.w);
    f[n] = max(f[n], g[n]);
    upd(1,1,N,vis[n][0],vis[n][1],g[n]-f[n]);
}

int main(){
    scanf("%d",&N);
    for(i=1;i<N;i++){
        scanf("%d%d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    dfs2(1,0);
    scanf("%d",&M);
    for(i=1;i<=M;i++){
        scanf("%d%d%d",&x,&y,&w);
        int l = lca(x, y);
        vec[l].push_back({x,y,w});
    }
    solve(1,0);
    printf("%d\n",f[1]);
    return 0;
}

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

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
election_campaign.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d",&M);
      |     ~~~~~^~~~~~~~~
election_campaign.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         scanf("%d%d%d",&x,&y,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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