oj.uz

Submission #624911

# Submission time Handle Problem Language Result Execution time Memory
624911 2022-08-09T03:22:02 Z messiuuuuu Toll (APIO13_toll) C++14
100 / 100
 1517 ms 13260 KB 
/*
GLORY GLORY MAN UNITED
*/

#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 <pii> save;
    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);
        save.pb({v, lab[v]});
        lab[u] += lab[v];
        lab[v] = u;
    }
    inline void undo(){
        int v = save.back().fi;
        lab[v] = save.back().se;
        lab[lab[v]] -= lab[v];
    }
    inline void clear(){
        lab.clear();
        save.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:125:9: warning: unused variable 'mophat' [-Wunused-variable]
  125 |     int mophat = mask;
      |         ^~~~~~
toll.cpp: In function 'int main()':
toll.cpp:224:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:225:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 140 ms 13132 KB Output is correct
8 Correct 148 ms 13136 KB Output is correct
9 Correct 143 ms 13116 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 140 ms 13132 KB Output is correct
8 Correct 148 ms 13136 KB Output is correct
9 Correct 143 ms 13116 KB Output is correct
10 Correct 1161 ms 13260 KB Output is correct
11 Correct 1517 ms 13236 KB Output is correct
12 Correct 1504 ms 13200 KB Output is correct