oj.uz

Submission #532020

# Submission time Handle Problem Language Result Execution time Memory
532020 2022-03-02T03:48:18 Z fivefourthreeone Road Closures (APIO21_roads) C++17
0 / 100
 2000 ms 37596 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 = 100005;
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 + 1; // +1 because 'pos' will have position of largest value less than 'v'
    }
    ll gethighest(int k) {
        //cout << k << " " << N << " higher?" << endl;
        int pos = search(k);
        return qsum(pos-1);
    }
}bit[mxN];
vector<array<int, 3>> adj[mxN];
set<int> best[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 (auto [v, w, pos] : adj[u]) {
        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; 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 && !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;
}
/*int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    vector<ll> ans = minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
    for (int i= 0; i < 4; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}*/

Compilation message

roads.cpp: In function 'll dfs(int, int, int)':
roads.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     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:130: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]
  130 |         for (int j = 0; j < adj[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 12 ms 13184 KB Output is correct
3 Correct 13 ms 13232 KB Output is correct
4 Correct 16 ms 13132 KB Output is correct
5 Correct 7 ms 12748 KB Output is correct
6 Correct 7 ms 12748 KB Output is correct
7 Correct 7 ms 12808 KB Output is correct
8 Correct 11 ms 13100 KB Output is correct
9 Correct 12 ms 13252 KB Output is correct
10 Correct 7 ms 12800 KB Output is correct
11 Correct 7 ms 12876 KB Output is correct
12 Execution timed out 2088 ms 23532 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Execution timed out 2037 ms 37596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12824 KB Output is correct
2 Correct 7 ms 12832 KB Output is correct
3 Correct 7 ms 12748 KB Output is correct
4 Incorrect 7 ms 12864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12824 KB Output is correct
2 Correct 7 ms 12832 KB Output is correct
3 Correct 7 ms 12748 KB Output is correct
4 Incorrect 7 ms 12864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 31616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 31616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 12 ms 13184 KB Output is correct
3 Correct 13 ms 13232 KB Output is correct
4 Correct 16 ms 13132 KB Output is correct
5 Correct 7 ms 12748 KB Output is correct
6 Correct 7 ms 12748 KB Output is correct
7 Correct 7 ms 12808 KB Output is correct
8 Correct 11 ms 13100 KB Output is correct
9 Correct 12 ms 13252 KB Output is correct
10 Correct 7 ms 12800 KB Output is correct
11 Correct 7 ms 12876 KB Output is correct
12 Execution timed out 2088 ms 23532 KB Time limit exceeded
13 Halted 0 ms 0 KB -