oj.uz

Submission #532036

# Submission time Handle Problem Language Result Execution time Memory
532036 2022-03-02T04:11:13 Z fivefourthreeone Road Closures (APIO21_roads) C++17
22 / 100
 164 ms 49944 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl

using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 250005;
struct BIT {
    int N;
    vector<ll> arr;
    vector<ll> cnt;
    void init(int n) {
        N = n;
        arr.resize(N+1, 0);
        cnt.resize(N+1, 0);
    }
    void upd(int p, int x) {
        p++;
        while(p <= N) {
            arr[p] += x;
            cnt[p]++;
            p += p&-p;
        }
    }
    ll qsum(int p) {
        ll res = 0;
        p++;
        while(p > 0) {
            res += arr[p];
            p -= p&-p;
        }
        return res;
    }
    int search (int v) {
        int sum = 0;
        int pos = 0;
	    for(int i=16; i>=0; i--) {
		    if(pos + (1 << i) < N && sum + cnt[pos + (1 << i)] < v) {
			    sum += cnt[pos + (1 << i)];
			    pos += (1 << i);
		    }
	    }
	    return pos;
    }
    ll gethighest(int k) {
        //cout << k << " " << N << " higher?" << endl;
        if (k == 0)return 0;
        int pos = search(k);
        return qsum(pos);
    }
}bit[mxN];
vector<array<int, 3>> adj[mxN];
int deg[mxN];
bool done[mxN];
vector<int> here;
ll dp[mxN][2]; //dp[0] is cant use, dp[1] is can use
vector<int> all;
ll die[mxN];
ll dfs(int u, int p, int k) {
    if (done[u]) return -1;
    //cout << u << " in" << endl;
    here.push_back(u);
    done[u] = 1;
    vector<ll> compute;
    ll always = 0;
    for (int _ = 0; _ < adj[u].size(); _++) {
        int v = adj[u][_][0];
        int w = adj[u][_][1];
        int pos = adj[u][_][2];
        if (v == p)continue;
        if (deg[v] == k) {
            //cout << u << " " << v << " " << pos << " " << w << " bit update\n";
            bit[u].upd(pos, w);
            continue;
        } else if (deg[v] < k) break;
        dfs(v, u, k);
        always += dp[v][0];
        if (dp[v][1] + w - dp[v][0] > 0) {
            compute.senpai(dp[v][1] + w - dp[v][0]);   
        }
    }
    sort(compute.begin(), compute.end());
    dp[u][0] = bit[u].gethighest(k);
    dp[u][1] = bit[u].gethighest(k-1);
    ll curr = 0;
    for (int i = 0; i < compute.size(); i++) {
        //cout << i << " " << compute[i] << "\n";
        curr += compute[i];
        if (k-i-1 >= 0) dp[u][0] = max(dp[u][0], curr + bit[u].gethighest(k-i-1));
        if (k-i-2 >= 0) dp[u][1] = max(dp[u][1], curr + bit[u].gethighest(k-i-2));
    }
    dp[u][0] += always;
    dp[u][1] += always;
    //cout << u << " out " << dp[u][0] << " " << dp[u][1] << endl;
    return dp[u][0];
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
    all.resize(n);
    iota(all.begin(), all.end(), 0);
    ll tot = 0;
    for (int i = 0; i < n-1; i++) {
        adj[u[i]].senpai({v[i], w[i], 0});
        adj[v[i]].senpai({u[i], w[i], 0});
        deg[u[i]]++;
        deg[v[i]]++;
        tot += w[i];
    }
    for (int i = 0; i < n-1; i++) {
        die[max(deg[u[i]], deg[v[i]])] += w[i];
    }
    for (int i = 1; i < n; i++) {
        die[i] += die[i-1];
    }
    owo(i, 0, n) {
        sort(adj[i].begin(), adj[i].end(), [&](array<int, 3> a, array<int, 3> b) {
            return a[1] > b[1]; 
        });
        for (int j = 0; j < adj[i].size(); j++) {
            adj[i][j][2] = j;
        }
        sort(adj[i].begin(), adj[i].end(), [&](array<int, 3> a, array<int, 3> b) {
            return deg[a[0]] > deg[b[0]]; 
        });
        bit[i].init(deg[i]);
    }
    sort(all.begin(), all.end(), [&](int a, int b) {
        return deg[a] > deg[b];
    });
    vector<ll> res(n);
    for (int k = 1; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (deg[all[i]] <= k)break;
            if (!done[all[i]]) {
                res[k] += dfs(all[i], -1, k);
            }
        }
        res[k] += die[k];
        for (int u : here) {
            done[u] = false;
        }
        here.clear();
    }
    owo(i, 0, n) {
        res[i] = tot - res[i];
    }
    return res;
}

Compilation message

roads.cpp: In function 'll dfs(int, int, int)':
roads.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int _ = 0; _ < adj[u].size(); _++) {
      |                     ~~^~~~~~~~~~~~~~~
roads.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < compute.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int j = 0; j < adj[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19788 KB Output is correct
2 Correct 13 ms 20148 KB Output is correct
3 Correct 14 ms 20280 KB Output is correct
4 Correct 13 ms 20172 KB Output is correct
5 Correct 11 ms 19876 KB Output is correct
6 Correct 11 ms 19888 KB Output is correct
7 Correct 11 ms 19848 KB Output is correct
8 Correct 11 ms 20172 KB Output is correct
9 Correct 12 ms 20172 KB Output is correct
10 Correct 10 ms 19880 KB Output is correct
11 Correct 12 ms 19880 KB Output is correct
12 Correct 68 ms 30588 KB Output is correct
13 Correct 109 ms 37680 KB Output is correct
14 Correct 105 ms 36544 KB Output is correct
15 Correct 114 ms 38360 KB Output is correct
16 Correct 136 ms 38732 KB Output is correct
17 Correct 126 ms 38852 KB Output is correct
18 Correct 10 ms 19788 KB Output is correct
19 Correct 93 ms 35948 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19788 KB Output is correct
2 Incorrect 82 ms 44656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19884 KB Output is correct
2 Correct 11 ms 19788 KB Output is correct
3 Correct 13 ms 19864 KB Output is correct
4 Incorrect 12 ms 19884 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19884 KB Output is correct
2 Correct 11 ms 19788 KB Output is correct
3 Correct 13 ms 19864 KB Output is correct
4 Incorrect 12 ms 19884 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 38236 KB Output is correct
2 Correct 164 ms 38340 KB Output is correct
3 Correct 114 ms 39736 KB Output is correct
4 Correct 131 ms 39228 KB Output is correct
5 Correct 117 ms 39748 KB Output is correct
6 Correct 99 ms 38340 KB Output is correct
7 Correct 115 ms 39668 KB Output is correct
8 Correct 94 ms 36612 KB Output is correct
9 Correct 144 ms 43972 KB Output is correct
10 Correct 130 ms 38960 KB Output is correct
11 Correct 106 ms 39844 KB Output is correct
12 Correct 109 ms 38240 KB Output is correct
13 Correct 11 ms 19888 KB Output is correct
14 Correct 76 ms 47036 KB Output is correct
15 Correct 85 ms 49944 KB Output is correct
16 Correct 13 ms 20280 KB Output is correct
17 Correct 13 ms 20172 KB Output is correct
18 Correct 13 ms 20172 KB Output is correct
19 Correct 13 ms 20152 KB Output is correct
20 Correct 13 ms 20172 KB Output is correct
21 Correct 93 ms 35960 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 38236 KB Output is correct
2 Correct 164 ms 38340 KB Output is correct
3 Correct 114 ms 39736 KB Output is correct
4 Correct 131 ms 39228 KB Output is correct
5 Correct 117 ms 39748 KB Output is correct
6 Correct 99 ms 38340 KB Output is correct
7 Correct 115 ms 39668 KB Output is correct
8 Correct 94 ms 36612 KB Output is correct
9 Correct 144 ms 43972 KB Output is correct
10 Correct 130 ms 38960 KB Output is correct
11 Correct 106 ms 39844 KB Output is correct
12 Correct 109 ms 38240 KB Output is correct
13 Correct 11 ms 19888 KB Output is correct
14 Correct 76 ms 47036 KB Output is correct
15 Correct 85 ms 49944 KB Output is correct
16 Correct 13 ms 20280 KB Output is correct
17 Correct 13 ms 20172 KB Output is correct
18 Correct 13 ms 20172 KB Output is correct
19 Correct 13 ms 20152 KB Output is correct
20 Correct 13 ms 20172 KB Output is correct
21 Correct 93 ms 35960 KB Output is correct
22 Correct 11 ms 19764 KB Output is correct
23 Correct 13 ms 19836 KB Output is correct
24 Correct 12 ms 19884 KB Output is correct
25 Incorrect 139 ms 36488 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19788 KB Output is correct
2 Correct 13 ms 20148 KB Output is correct
3 Correct 14 ms 20280 KB Output is correct
4 Correct 13 ms 20172 KB Output is correct
5 Correct 11 ms 19876 KB Output is correct
6 Correct 11 ms 19888 KB Output is correct
7 Correct 11 ms 19848 KB Output is correct
8 Correct 11 ms 20172 KB Output is correct
9 Correct 12 ms 20172 KB Output is correct
10 Correct 10 ms 19880 KB Output is correct
11 Correct 12 ms 19880 KB Output is correct
12 Correct 68 ms 30588 KB Output is correct
13 Correct 109 ms 37680 KB Output is correct
14 Correct 105 ms 36544 KB Output is correct
15 Correct 114 ms 38360 KB Output is correct
16 Correct 136 ms 38732 KB Output is correct
17 Correct 126 ms 38852 KB Output is correct
18 Correct 10 ms 19788 KB Output is correct
19 Correct 93 ms 35948 KB Output is correct
20 Correct 11 ms 19788 KB Output is correct
21 Incorrect 82 ms 44656 KB Output isn't correct
22 Halted 0 ms 0 KB -