Submission #549453

#	Time	Username	Problem	Language	Result	Execution time	Memory
549453		skyvn97	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	297 ms	39404 KiB

election_campaign

#include<bits/stdc++.h>
#define MAX   100100
#define LOG   17
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
class SegmentTree {
    private:
    int n;
    vector<int> lazy;
    void update(int i,int l,int r,int u,int v,int c) {
        if (l>v || r<u || l>r || v<u) return;
        if (u<=l && r<=v) {
            lazy[i]+=c;
            return;
        }
        int m=(l+r)>>1;
        update(2*i,l,m,u,v,c);
        update(2*i+1,m+1,r,u,v,c);
    }
    public:
    SegmentTree() {
        n=0;
    }
    SegmentTree(int n) {
        this->n=n;
        lazy.assign(4*n+7,0);
    }
    void update(int l,int r,int c) {
        update(1,1,n,l,r,c);
    }
    int get(int x) const {
        int res=0;
        int i=1;
        int l=1;
        int r=n;
        while (true) {
            res+=lazy[i];
            if (l==r) return (res);
            int m=(l+r)>>1;
            if (x>m) {
                i=2*i+1;
                l=m+1;
            } else {
                i=2*i;
                r=m;
            }
        }
    }
};
struct Req {
    int u,v,c;
    Req() {
        u=v=c=0;
    }
    void input(void) {
        scanf("%d%d%d",&u,&v,&c);
    }
};
Req req[MAX];
vector<int> adj[MAX];
int n,m,cnt;
int sta[MAX],fin[MAX],high[MAX],par[MAX][LOG+1];
vector<int> reqAt[MAX];
int f[MAX],sumF[MAX];
SegmentTree myit;
void loadTree(void) {
    scanf("%d",&n);
    REP(love,n-1) {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    scanf("%d",&m);
    FOR(i,1,m) req[i].input();
}
void dfs(int u) {
    sta[u]=++cnt;
    FORE(it,adj[u]) if (*it!=par[u][0]) {
        int v=*it;
        high[v]=high[u]+1;
        par[v][0]=u;
        dfs(v);
    }
    fin[u]=cnt;
}
int LCA(int u,int v) {
    if (high[u]<high[v]) return (LCA(v,u));
    FORD(i,LOG,0) if (high[par[u][i]]>=high[v]) u=par[u][i];
    if (u==v) return (u);
    FORD(i,LOG,0) if (par[u][i]!=par[v][i]) {
        u=par[u][i];
        v=par[v][i];
    }
    return (par[u][0]);
}
int jump(int u,int h) {
    FORD(i,LOG,0) if (high[par[u][i]]>=h) u=par[u][i];
    return (u);
}
void prepare(void) {
    high[0]=-1;
    dfs(1);
    FOR(j,1,LOG) FOR(i,1,n) par[i][j]=par[par[i][j-1]][j-1];
    FOR(i,1,m) reqAt[LCA(req[i].u,req[i].v)].push_back(i);
    myit=SegmentTree(n);
}
void dp(int u) {
    FORE(it,adj[u]) if (*it!=par[u][0]) {
        int v=*it;
        dp(v);
        sumF[u]+=f[v];
    }
    f[u]=sumF[u];
    /*printf("To calculate %d\n",u);
    FOR(i,1,n) if (LCA(i,u)==u) printf("Value of %d is %d\n",i,myit.get(sta[i]));
    printf("END\n");*/
    FORE(it,reqAt[u]) {
        int x=req[*it].u;
        int y=req[*it].v;
        int px=jump(x,high[u]+1);
        int py=jump(y,high[u]+1);
        int tmp=sumF[u];
        if (x!=u) tmp+=myit.get(sta[x])-f[px];
        if (y!=u) tmp+=myit.get(sta[y])-f[py];
        //printf("With req %d (%d,%d,%d) at %d have %d\n",*it,req[*it].u,req[*it].v,req[*it].c,u,tmp+req[*it].c);
        f[u]=max(f[u],tmp+req[*it].c);
    }
    FORE(it,adj[u]) if (*it!=par[u][0]) {
        int v=*it;
        myit.update(sta[v],fin[v],sumF[u]-f[v]);
    }
    myit.update(sta[u],sta[u],sumF[u]);
    //printf("F %d is %d\n",u,f[u]);
}
void process(void) {
    dp(1);
    printf("%d\n",f[1]);
}
int main(void) {
    //freopen("test.in","r",stdin);
    loadTree();
    prepare();
    process();
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void loadTree()':
election_campaign.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
election_campaign.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
election_campaign.cpp: In member function 'void Req::input()':
election_campaign.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d%d%d",&u,&v,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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