oj.uz

Submission #718653

# Submission time Handle Problem Language Result Execution time Memory
718653 2023-04-04T13:17:57 Z keta_tsimakuridze Toll (APIO13_toll) C++14
100 / 100
 2187 ms 17728 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, h[N], par[N], up[N], p[N], P[N];
ll SZ[N], sz[N];
ll cur = 0;
vector<pair<int,int>> V[N];
void dfs0(int u, int p) {
    h[u] = h[p] + 1;
    SZ[u] = sz[u];
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f;
        if(v == p) continue;
        par[v] = u;
        up[v] = (V[u][i].s == 0 ? 0 : 1e6);
        dfs0(v, u);
        SZ[u] += SZ[v];
    }
}
void UP(int u, int v, int w) {
    while(u != v) {
        if(h[u] < h[v]) swap(u, v);
        up[u] = min(up[u], w);
        u = par[u];
    }
}
void dfs(int u, int p) {
    cur += (ll)up[u] * SZ[u];
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f;
        if(v == p) continue;
        dfs(v, u);
    }
}
int find(int x){
    return (p[x] == x ? p[x] : p[x] = find(p[x]));
}
int find1(int x) {
    return (P[x] == x ? P[x] : P[x] = find1(P[x]));
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, pair<int,int> > > E,ex;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        E.push_back({w, {u, v}});
    }
    for(int i = 0; i < k; i++) {
        int u, v; cin >> u >> v;
        E.push_back({0, {u, v}});
    }
    for(int i = 1; i <= n; i++) cin >> sz[i];
    sort(E.begin(), E.end());
    vector<int> X(E.size());
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = k; i < E.size(); i++) {
        int u = E[i].s.f, v = E[i].s.s;
        if(find(u) == find(v)) continue;
        X[i] = 1;
        p[find(u)] = find(v);
    }
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 0; i < E.size(); i++) {
        int u = E[i].s.f, v = E[i].s.s;
        if(find(u) == find(v)) {
            if(X[i]) ex.push_back(E[i]);
            X[i] = 0;
            continue;
        }
        X[i] = 1;
        p[find(u)] = find(v);
    }
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = k; i < E.size(); i++) {
        int u = E[i].s.f, v = E[i].s.s;
        if(!X[i] || find(u) == find(v)) continue;
        sz[find(v)] += sz[find(u)];
        p[find(u)] = find(v);
    }
    vector<int> x;
    for(int i = 1; i <= n; i++) if(find(i) == i) x.push_back(i);
    ll ans = 0;
    for(int mask = 1; mask < (1 << k); mask++) {
        for(int i = 0; i < x.size(); i++) V[x[i]].clear(), P[x[i]] = x[i];
        int F = 0;
        for(int i = 0; i < k; i++) {
            if((1 << i) & mask) {
                int u = E[i].s.f, v = E[i].s.s;
                u = find(u); v = find(v);
                if(find1(u) == find1(v)) F = 1;
                P[find1(u)] = find1(v);
                V[v].push_back({u, 1});
                V[u].push_back({v, 1});
            }
        }
        if(F) continue;
        vector<int> f(ex.size());
        for(int i = 0; i < ex.size(); i++) {
            int u = ex[i].s.f, v = ex[i].s.s;
            u = find(u); v = find(v);
            if(find1(u) != find1(v)) {
                P[find1(u)] = find1(v);
                V[v].push_back({u, 0});
                V[u].push_back({v, 0});
            } else f[i] = 1;
        }
        dfs0(find(1), 0);

        for(int i = 0; i < ex.size(); i++) {
            if(!f[i]) continue;
            int u = ex[i].s.f, v = ex[i].s.s, w = ex[i].f;
            u = find(u); v = find(v);
            UP(u, v, w);
        }
        cur = 0;
        dfs(find(1), 0);
        ans = max(ans, cur);
    } cout << ans;
 }

Compilation message

toll.cpp: In function 'void dfs0(int, int)':
toll.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
toll.cpp: In function 'void dfs(int, int)':
toll.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
toll.cpp: At global scope:
toll.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main(){
      | ^~~~
toll.cpp: In function 'int main()':
toll.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = k; i < E.size(); i++) {
      |                    ~~^~~~~~~~~~
toll.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < E.size(); i++) {
      |                    ~~^~~~~~~~~~
toll.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = k; i < E.size(); i++) {
      |                    ~~^~~~~~~~~~
toll.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int i = 0; i < x.size(); i++) V[x[i]].clear(), P[x[i]] = x[i];
      |                        ~~^~~~~~~~~~
toll.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i = 0; i < ex.size(); i++) {
      |                        ~~^~~~~~~~~~~
toll.cpp:116:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int i = 0; i < ex.size(); i++) {
      |                        ~~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 7 ms 5288 KB Output is correct
6 Correct 8 ms 5332 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 7 ms 5288 KB Output is correct
6 Correct 8 ms 5332 KB Output is correct
7 Correct 198 ms 17628 KB Output is correct
8 Correct 233 ms 17616 KB Output is correct
9 Correct 252 ms 17588 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 6 ms 4948 KB Output is correct
5 Correct 7 ms 5288 KB Output is correct
6 Correct 8 ms 5332 KB Output is correct
7 Correct 198 ms 17628 KB Output is correct
8 Correct 233 ms 17616 KB Output is correct
9 Correct 252 ms 17588 KB Output is correct
10 Correct 1658 ms 17728 KB Output is correct
11 Correct 2169 ms 17700 KB Output is correct
12 Correct 2187 ms 17708 KB Output is correct