Submission #946022

#	Time	Username	Problem	Language	Result	Execution time	Memory
946022		hariaakas646	Election Campaign (JOI15_election_campaign)	C++17	20 / 100	1020 ms	55464 KiB

election_campaign

#include <bits/stdc++.h>
 
using namespace std;
 
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, l, r) for(int i=l; i<r; i++)
#define frange(i, l) forr(i, 0, l)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef long long lli;
typedef vector<vi> vvi;
typedef vector<lli> vll;
typedef vector<bool> vb;
typedef set<int> seti;
typedef multiset<int> mseti;
 
void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

vvi liftv;
vvi graph;
vi depth;

void dfs(int x, int p) {
    depth[x] = depth[p] + 1;
    liftv[0][x] = p;
    for(auto e : graph[x]) {
        if(e != p) {
            dfs(e, x);
        }
    }
}

int lift(int x, int c) {
    frange(i, 20) {
        if(c & (1<<i)) {
            x = liftv[i][x];
        }
    }
    return x;
}

int lca(int x, int y) {
    if(depth[y] > depth[x]) swap(x, y);
    x = lift(x, depth[x] - depth[y]);
    if(x == y) return x;
    for(int i=19; i>=0; i--) {
        int xt = liftv[i][x];
        int yt = liftv[i][y];
        if(xt != yt) {
            x = xt;
            y = yt;
        }
    }
    return liftv[0][x];
}

vvi st;
vvi lc;
vll cost;
lli tot = 0;

map<int, lli> dfs2(int x, int p) {
    map<int, lli> mv;
    for(auto e : st[x]) {
        mv[e] += 0;
    }
    for(auto e : graph[x]) {
        if(e != p) {
            map<int, lli> out = dfs2(e, x);
            if(mv.size() < out.size()) swap(mv, out);
            for(auto pi : out) {
                mv[pi.f] += pi.s;
            }
        }
    }
    lli ma = -1e18;
    
    // printf("%d\n", x);
    // for(auto e : mv) {
    //     printf("%d %lld\n", e.f, e.s);
    // }
    for(auto e : lc[x]) {
        ma = max(ma, mv[e] + cost[e]);
        mv.erase(e);
    }
    
    
    if(ma > 0) {
        tot += ma;
        for(auto e : mv) {
            mv[e.f] -= ma;
        }
    }
    return mv;
    
}

int main() {
    // usaco();
    int n;
    scd(n);
    graph = vvi(n+1);
    frange(i, n-1) {
        int a, b;
        scd(a);
        scd(b);
        graph[a].pb(b);
        graph[b].pb(a);
    }
    depth = vi(n+1);
    liftv = vvi(20, vi(n+1));
    dfs(1, 0);
    

    forr(i, 1, 20) {
        forr(j, 1, n+1) {
            liftv[i][j] = liftv[i-1][liftv[i-1][j]];
        }
    }

    st = lc = vvi(n+1);
    int m;
    scd(m);
    cost = vll(m);
    forr(i, 0, m) {
        int a, b;
        scd(a);
        scd(b);
        sclld(cost[i]);
        lc[lca(a, b)].pb(i);
        st[a].pb(i);
        st[b].pb(i);
    }

    dfs2(1, 0);
    printf("%lld", tot);
}   

Compilation message (stderr)

election_campaign.cpp: In function 'void usaco()':
election_campaign.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election_campaign.cpp:113:5: note: in expansion of macro 'scd'
  113 |     scd(n);
      |     ^~~
election_campaign.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election_campaign.cpp:117:9: note: in expansion of macro 'scd'
  117 |         scd(a);
      |         ^~~
election_campaign.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election_campaign.cpp:118:9: note: in expansion of macro 'scd'
  118 |         scd(b);
      |         ^~~
election_campaign.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election_campaign.cpp:135:5: note: in expansion of macro 'scd'
  135 |     scd(m);
      |     ^~~
election_campaign.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election_campaign.cpp:139:9: note: in expansion of macro 'scd'
  139 |         scd(a);
      |         ^~~
election_campaign.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election_campaign.cpp:140:9: note: in expansion of macro 'scd'
  140 |         scd(b);
      |         ^~~
election_campaign.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define sclld(t) scanf("%lld", &t)
      |                  ~~~~~^~~~~~~~~~~~
election_campaign.cpp:141:9: note: in expansion of macro 'sclld'
  141 |         sclld(cost[i]);
      |         ^~~~~

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