oj.uz

답안 #513686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
513686 2022-01-17T12:15:49 Z pokmui9909 통행료 (APIO13_toll) C++17
78 / 100
 2500 ms 29332 KB 
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
using ll = long long;
 
#define x first
#define y second
class UnionFind{
public:
    UnionFind(ll S){
        p.resize(S + 5, -1);
    }
    vector<ll> p;
    ll Find(ll n){
      	if(p[n] < 0) return n;
      	else return p[n] = Find(p[n]);
    }
    void Union(ll a, ll b){
        a = Find(a), b = Find(b);
        if (a == b) return;
        p[a] += p[b];
        p[b] = a;
    }
    bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
};
ll N, M, K;
struct Edge{
    ll u, v, c;
    bool operator<(const Edge &r)const{
        return c < r.c;
    }
};
vector<Edge> E;
vector<Edge> add;
ll P[100005];
UnionFind S(100005);
vector<pair<ll, ll>> G[100005];
ll Par[100005];
ll depth[100005];
ll MinCost[100005];
ll cnt[100005];
vector<Edge> rem;
vector<ll> CG[100005];
vector<Edge> NE;
vector<Edge> X;
ll NP[100005];
ll num[100005];
ll check[30][30];
void dfs1(ll n, ll p){
    Par[n] = p;
    for(auto i : G[n]){
        if(i.x == p) continue;
        depth[i.x] = depth[n] + 1;
        dfs1(i.x, n);
    }
}
ll sum = 0, Comps = 0;
void dfs2(ll n, ll p){
    cnt[n] = NP[n];
    for(auto i : G[n]){
        ll nx = i.x, c = i.y;
        if(nx == p) continue;
        dfs2(nx, n);
        cnt[n] += cnt[nx];
        if(c == -1){
            sum += MinCost[nx] * cnt[nx];
        }
    }
}
void dfs3(ll n){
    num[n] = Comps;
    NP[Comps] += P[n];
    for(auto j : G[n]){
        if(num[j.x]) continue;
        dfs3(j.x);
    }
}
 
void init(){
    for(int i = 0; i < 25; i++){
        for(int j = 0; j < 25; j++){
            check[i][j] = 1e18;
        }
    }
    for(int i = 0; i < K; i++){
        ll u = add[i].u, v = add[i].v;
        S.Union(u, v);
    }
    for(int i = 0; i < E.size(); i++){
        ll u = E[i].u, v = E[i].v, c = E[i].c;
        if(S.Same(u, v)){
            rem.push_back({u, v, c});
        } else {
            G[u].push_back({v, c});
            G[v].push_back({u, c});
            S.Union(u, v);
        }
    }
    for(int i = 1; i <= N; i++){
        if(num[i]) continue;
        Comps++;
        dfs3(i);
    }
    for(int i = 0; i < rem.size(); i++){
        ll u = rem[i].u, v = rem[i].v, c = rem[i].c;
        u = num[u], v = num[v];
        if(u == v) continue;
        if(u > v) swap(u, v);
        check[u][v] = min(check[u][v], c);
    }
    for(int i = 1; i < 25; i++){
        for(int j = i + 1; j < 25; j++){
            if(check[i][j] >= 1e18) continue;
            NE.push_back({i, j, check[i][j]});
        }
    }
    sort(NE.begin(), NE.end());
    for(int i = 0; i < add.size(); i++){
        add[i].u = num[add[i].u];
        add[i].v = num[add[i].v];
    }
}
 
ll Solve(ll bit){
    double T1 = 0, T2 = 0;
    for(int i = 0; i < 25; i++){
        G[i].clear();
        MinCost[i] = 1e18;
        S.p[i] = -1;
    }
    X.clear();
    T1 = time(NULL);
    for(int i = 0; i < K; i++){
        if(bit & (1 << i)){
            ll u = add[i].u, v = add[i].v;
            if(S.Same(u, v)) return -1;
            S.Union(u, v);
            G[u].push_back({v, -1});
            G[v].push_back({u, -1});
        }
    }
    T2 = time(NULL);
    assert(T2 - T1 <= 5);
    T1 = time(NULL);
    for(int i = 0; i < NE.size(); i++){
        ll u = NE[i].u, v = NE[i].v, c = NE[i].c;
        if(S.Same(u, v)){
            X.push_back({u, v, c});
            continue;
        }
        S.Union(u, v);
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }
    T2 = time(NULL);
    assert(T2 - T1 <= 5);
    T1 = time(NULL);
    dfs1(1, -1);
    T2 = time(NULL);
    assert(T2 - T1 <= 5);
    T1 = time(NULL);
    for(int i = 0; i < X.size(); i++){
        ll u = X[i].u, v = X[i].v, c = X[i].c;
        if(depth[u] < depth[v]) swap(u, v);
        while(depth[u] > depth[v]){
            MinCost[u] = min(MinCost[u], c);
            u = Par[u];
        }
        while(u != v){
            MinCost[u] = min(MinCost[u], c);
            MinCost[v] = min(MinCost[v], c);
            u = Par[u];
            v = Par[v];
        }
    }
    T2 = time(NULL);
    assert(T2 - T1 <= 5);
    T1 = time(NULL);
    sum = 0;
    dfs2(1, 0);
    T2 = time(NULL);
    assert(T2 - T1 <= 5);
    return sum;
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
 
    double T3 = time(NULL);
    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        ll u, v, c; cin >> u >> v >> c;
        E.push_back({u, v, c});
    }
    for(int i = 1; i <= K; i++){
        ll u, v; cin >> u >> v;
        add.push_back({u, v});
    }
    for(int i = 1; i <= N; i++){
        cin >> P[i];
    }
    sort(E.begin(), E.end());
    init();
    double T4 = time(NULL);
    assert(T4 - T3 <= 100);
    ll ans = 0;
    double S = 0;
    for(int i = 0; i < (1 << K); i++){
        double T1 = time(NULL);
        ans = max(ans, Solve(i));
        double T2 = time(NULL);
        S += T2 - T1;
        assert(S <= 10 * i);
    }
    cout << ans;
}

Compilation message

toll.cpp: In function 'void init()':
toll.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0; i < E.size(); i++){
      |                    ~~^~~~~~~~~~
toll.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < rem.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i = 0; i < add.size(); i++){
      |                    ~~^~~~~~~~~~~~
toll.cpp: In function 'll Solve(ll)':
toll.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(int i = 0; i < NE.size(); i++){
      |                    ~~^~~~~~~~~~~
toll.cpp:163:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i = 0; i < X.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 3 ms 5756 KB Output is correct
3 Correct 5 ms 5816 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 3 ms 5756 KB Output is correct
3 Correct 5 ms 5816 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct
5 Correct 6 ms 6156 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 3 ms 5756 KB Output is correct
3 Correct 5 ms 5816 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct
5 Correct 6 ms 6156 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 217 ms 29284 KB Output is correct
8 Correct 342 ms 29328 KB Output is correct
9 Correct 294 ms 29244 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 3 ms 5756 KB Output is correct
3 Correct 5 ms 5816 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct
5 Correct 6 ms 6156 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 217 ms 29284 KB Output is correct
8 Correct 342 ms 29328 KB Output is correct
9 Correct 294 ms 29244 KB Output is correct
10 Correct 1406 ms 29320 KB Output is correct
11 Execution timed out 2585 ms 29332 KB Time limit exceeded
12 Halted 0 ms 0 KB -