oj.uz

답안 #619091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619091 2022-08-02T09:49:20 Z Do_you_copy 통행료 (APIO13_toll) C++17
100 / 100
 1539 ms 8804 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 <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:121:9: warning: unused variable 'mophat' [-Wunused-variable]
  121 |     int mophat = mask;
      |         ^~~~~~
toll.cpp: In function 'int main()':
toll.cpp:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:221:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 4 ms 508 KB Output is correct
6 Correct 3 ms 464 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 4 ms 508 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 162 ms 8668 KB Output is correct
8 Correct 152 ms 8716 KB Output is correct
9 Correct 152 ms 8804 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 4 ms 508 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 162 ms 8668 KB Output is correct
8 Correct 152 ms 8716 KB Output is correct
9 Correct 152 ms 8804 KB Output is correct
10 Correct 1203 ms 8780 KB Output is correct
11 Correct 1539 ms 8772 KB Output is correct
12 Correct 1529 ms 8788 KB Output is correct