oj.uz

Submission #946036

# Submission time Handle Problem Language Result Execution time Memory
946036 2024-03-14T09:48:34 Z hariaakas646 Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 48952 KB 
#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;
vii pos;

map<int, lli> dfs2(int x, int p) {
    map<int, lli> mv;
    
    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;
    mv[x] = 0;
    // 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[pos[e].f] + mv[pos[e].s] + cost[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);
    pos = vii(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);
        pos[i] = mp(a, b);
    }

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

Compilation message

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:111:5: note: in expansion of macro 'scd'
  111 |     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:115:9: note: in expansion of macro 'scd'
  115 |         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:116:9: note: in expansion of macro 'scd'
  116 |         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:133:5: note: in expansion of macro 'scd'
  133 |     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:138:9: note: in expansion of macro 'scd'
  138 |         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:139:9: note: in expansion of macro 'scd'
  139 |         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:140:9: note: in expansion of macro 'sclld'
  140 |         sclld(cost[i]);
      |         ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 137 ms 27660 KB Output is correct
6 Correct 95 ms 45232 KB Output is correct
7 Correct 107 ms 38292 KB Output is correct
8 Correct 93 ms 25428 KB Output is correct
9 Correct 122 ms 36300 KB Output is correct
10 Correct 97 ms 26212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Execution timed out 1070 ms 48952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Execution timed out 1070 ms 48952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 31688 KB Output is correct
2 Execution timed out 1063 ms 47936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 137 ms 27660 KB Output is correct
6 Correct 95 ms 45232 KB Output is correct
7 Correct 107 ms 38292 KB Output is correct
8 Correct 93 ms 25428 KB Output is correct
9 Correct 122 ms 36300 KB Output is correct
10 Correct 97 ms 26212 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 940 KB Output is correct
13 Correct 5 ms 860 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 2 ms 860 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 137 ms 27660 KB Output is correct
6 Correct 95 ms 45232 KB Output is correct
7 Correct 107 ms 38292 KB Output is correct
8 Correct 93 ms 25428 KB Output is correct
9 Correct 122 ms 36300 KB Output is correct
10 Correct 97 ms 26212 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 3 ms 1112 KB Output is correct
14 Execution timed out 1070 ms 48952 KB Time limit exceeded
15 Halted 0 ms 0 KB -