oj.uz

Submission #619061

# Submission time Handle Problem Language Result Execution time Memory
619061 2022-08-02T09:37:02 Z Do_you_copy Toll (APIO13_toll) C++17
100 / 100
 1524 ms 12032 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 20;
const int maxM = 3e5 + 20;
const int maxK = 30;
const int inf = 0x3f3f3f3f;
int n, m, k;

struct TEdge{
    int u, v, w;
    bool operator < (const TEdge &other){
        return w < other.w;
    }
};
TEdge a[2 * maxM];

vector <int> edge;
struct TDSU{
    vector <int> lab;
    TDSU(){}
    TDSU(int _n){
        lab.resize(_n, -1);
    }
    inline void resize(int _n){
        lab.resize(_n, -1);
    }
    inline int find(int u){
        if (lab[u] < 0) return u;
        return lab[u] = find(lab[u]);
    }
    inline void merge(int u, int v){
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
    }
    inline void clear(){
        lab.clear();
    }
    inline void reset(int _n){
        clear();
        resize(_n);
    }
};

TDSU dsu;
int p[maxN];
int id[maxN];
int depth[maxK];
int node_cnt = 0;
ll sum[maxK];
vector <TEdge> required;
bool mark[maxK];
ll res = 0;
vector <pii> adj[maxK];
ll sm[maxK];
int par[maxK];

void dfs(int u, int p){
    sm[u] = sum[u];
    par[u] = p;
    depth[u] = depth[p] + 1;
    for (auto i: adj[u]){
        if (i.fi == p) continue;
        if (i.se != -inf) mark[i.fi] = 1;
        dfs(i.fi, u);
        sm[u] += sm[i.fi];
    }
}

void update(int u, int v, int w){
    if (depth[u] < depth[v]) swap(u, v);
    while (depth[u] != depth[v]){
        if (!mark[u]) res += sm[u] * w;
        sm[u] = 0;
        u = par[u];
    }
    while (u != v){
        if (!mark[u]) res += sm[u] * w;
        if (!mark[v]) res += sm[v] * w;
        sm[u] = sm[v] = 0;
        u = par[u];
        v = par[v];
    }
}

ll cal(int mask){
    res = 0;
    int mophat = mask;
    fill(mark, mark + node_cnt + 1, 0);
    dsu.reset(node_cnt + 1);
    for (int i = 1; i <= node_cnt; ++i) adj[i].clear();
    while (mask){
        int t = mask & -mask;
        int i = __lg(t) + 1;
        int u = a[i].u; int v = a[i].v;
        int x = dsu.find(u), y = dsu.find(v);
        if (x == y){
            return 0;
        }
        dsu.merge(x, y);
        adj[u].pb({v, -inf});
        adj[v].pb({u, -inf});
        mask -= t;
    }
    vector <TEdge> check;
    for (auto i: required){
        int x = dsu.find(i.u), y = dsu.find(i.v);
        if (x != y){
            dsu.merge(x, y);
            adj[i.u].pb({i.v, i.w});
            adj[i.v].pb({i.u, i.w});
        }
        else check.pb(i);
    }
    dfs(1, 0);
    for (auto i: check){
        update(i.u, i.v, i.w);
    }
    //cerr << mophat << " " << res << "\n";
    return res;
}

void Init(){
    cin >> n >> m >> k;
    for (int i = k + 1; i <= m + k; ++i){
        cin >> a[i].u >> a[i].v >> a[i].w;
    }
    for (int i = 1; i <= k; ++i){
        cin >> a[i].u >> a[i].v;
        a[i].w = -inf;
    }
    for (int i = 1; i <= n; ++i) cin >> p[i];
    sort(a + k + 1, a + m + k + 1);
    dsu.reset(n + 1);
    for (int i = 1; i <= k; ++i){
        int u = a[i].u, v = a[i].v;
        int x = dsu.find(u), y = dsu.find(v);
        if (x != y){
            dsu.merge(x, y);
        }
    }
    for (int i = k + 1; i <= m + k; ++i){
        int u = a[i].u, v = a[i].v;
        int x = dsu.find(u), y = dsu.find(v);
        if (x != y){
            edge.pb(i);
            dsu.merge(x, y);
        }
    }
    dsu.reset(n + 1);
    for (const int &i: edge){
        int u = a[i].u, v = a[i].v;
        int x = dsu.find(u), y = dsu.find(v);
        dsu.merge(x, y);
    }
    for (int i = 1; i <= n; ++i){
        int j = dsu.find(i);
        if (!id[j]) id[j] = ++node_cnt;
        sum[id[i] = id[j]] += p[i];
    }
    for (int i = 1; i <= k + m; ++i){
        a[i].u = id[a[i].u];
        a[i].v = id[a[i].v];
    }
    dsu.reset(node_cnt + 1);
    edge.clear();
    for (int i = k + 1; i <= k + m; ++i){
        int u = a[i].u, v = a[i].v;
        int x = dsu.find(u), y = dsu.find(v);
        if (x != y){
            edge.pb(i);
            dsu.merge(x, y);
        }
    }
    for (const int &i: edge) required.pb(a[i]);
    ll ans = 0;
    for (int i = 1; i < 1 << k; ++i){
        ans = max(ans, cal(i));
    }
    cerr << ans;
    cout << ans;
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

toll.cpp: In function 'll cal(int)':
toll.cpp:113:9: warning: unused variable 'mophat' [-Wunused-variable]
  113 |     int mophat = mask;
      |         ^~~~~~
toll.cpp: In function 'int main()':
toll.cpp:212:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:213:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 420 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 420 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 147 ms 11968 KB Output is correct
8 Correct 152 ms 11964 KB Output is correct
9 Correct 164 ms 11980 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 420 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 147 ms 11968 KB Output is correct
8 Correct 152 ms 11964 KB Output is correct
9 Correct 164 ms 11980 KB Output is correct
10 Correct 1118 ms 12032 KB Output is correct
11 Correct 1524 ms 12008 KB Output is correct
12 Correct 1467 ms 12012 KB Output is correct