oj.uz

Submission #159374

# Submission time Handle Problem Language Result Execution time Memory
159374 2019-10-22T13:32:03 Z EntityIT Toll (APIO13_toll) C++14
78 / 100
 2500 ms 8572 KB 
#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int n, nRoad, nNewRoad, curTime;
LL ans;
vector<int> nPeople, newId, par, be;
vector<LL> nP, cnt;
struct Edge { int u, v, c; };
vector<Edge> road;
vector<pair<int, int> > newRoad;
vector<vector<pair<int, int> > > gr;

struct Dsu {
    vector<int> pSet;
    Dsu(int nV) {
        pSet.assign(nV + 5, 0);
        iota(pSet.begin(), pSet.end(), 0);
    }
    void reset(int nV) {
        pSet.assign(nV + 5, 0);
        iota(pSet.begin(), pSet.end(), 0);
    }
    int findSet(int i) { return i == pSet[i] ? i : pSet[i] = findSet(pSet[i]); }
    bool sameSet(int i, int j) { return findSet(i) == findSet(j); }
    void unionSet(int i, int j) {
        i = findSet(i); j = findSet(j);
        if (i == j) return ;
        pSet[i] = j;
    }
};

int getBit(int a, int bit) { return (a >> bit) & 1; }

void dfs(int u, int p) {
    cnt[u] = nP[u];
    be[u] = ++curTime;
    par[u] = p;
    for (auto pai : gr[u]) {
        int v = pai.first;
        if (v == p) continue ;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
}

int main() {
//    freopen("input", "r", stdin);

    scanf(" %d %d %d", &n, &nRoad, &nNewRoad);

    road.assign(nRoad, {} );
    for (int i = 0; i < nRoad; ++i) {
        int u, v, c; scanf(" %d %d %d", &u, &v, &c);
        road[i] = { u, v, c };
    }
    sort(road.begin(), road.end(), [](Edge i, Edge j) { return i.c < j.c; } );

    newRoad.assign(nNewRoad, {} );
    for (int i = 0; i < nNewRoad; ++i) {
        int u, v; scanf(" %d %d", &u, &v);
        newRoad[i] = { u, v };
    }

    nPeople.assign(n + 5, 0);
    for (int i = 1; i <= n; ++i) scanf(" %d", &nPeople[i]);

    Dsu dsu(n), dsu2(n);
    for (auto aNewRoad : newRoad) dsu2.unionSet(aNewRoad.first, aNewRoad.second);
    for (auto aRoad : road) {
        int u = aRoad.u, v = aRoad.v;
        if (!dsu2.sameSet(u, v) ) {
            dsu2.unionSet(u, v);
            dsu.unionSet(u, v);
        }
    }

    newId.assign(n + 5, 0);
    int iId = 0;
    for (int i = 1; i <= n; ++i) {
        if (!newId[dsu.findSet(i)]) newId[dsu.findSet(i)] = ++iId;
    }

    vector<Edge> staredRoad;
    set<pair<int, int> > addedRoad;
    for (auto aRoad : road) {
        int u = aRoad.u, v = aRoad.v, c = aRoad.c;
        u = newId[dsu.findSet(u)];
        v = newId[dsu.findSet(v)];
        if (u > v) swap(u, v);
        if (u != v && !addedRoad.count(pair<int, int>{ u, v } ) ) {
            staredRoad.push_back( { u, v, c } );
            addedRoad.insert( { u, v } );
        }
    }

    assert( (int)addedRoad.size() <= 441);

    for (auto &aNewRoad : newRoad) {
        aNewRoad.first = newId[dsu.findSet(aNewRoad.first)];
        aNewRoad.second = newId[dsu.findSet(aNewRoad.second)];
    }

    nP.assign(n + 5, 0);
    for (int i = 1; i <= n; ++i) nP[ newId[dsu.findSet(i)] ] += nPeople[i];

    cnt.assign(iId + 5, 0);
    par.assign(iId + 5, 0);
    be.assign(iId + 5, 0);
    for (int mask = 0; mask < (1 << nNewRoad); ++mask) {
        bool valid = 1;
        Dsu check(iId);
        gr.assign(iId + 5, vector<pair<int, int> >() );
        for (int i = 0; i < nNewRoad; ++i) if (getBit(mask, i) ) {
            int u = newRoad[i].first, v = newRoad[i].second;
            if (check.sameSet(u, v) ) {
                valid = 0;
                break ;
            }
            check.unionSet(u, v);
            gr[u].emplace_back(v, 0);
            gr[v].emplace_back(u, 0);
        }
        if (!valid) continue ;

        for (auto aRoad : staredRoad) {
            int u = aRoad.u, v = aRoad.v, c = aRoad.c;
            if (check.sameSet(u, v) ) continue ;
            check.unionSet(u, v);
            gr[u].emplace_back(v, c);
            gr[v].emplace_back(u, c);
        }

        curTime = 0;
        dfs(1, 0);

        LL ret = 0;
        dsu.reset(iId);
        for (auto aRoad : staredRoad) {
            int u = dsu.findSet(aRoad.u), v = dsu.findSet(aRoad.v), c = aRoad.c;
            while (u != v) {
                if (be[u] < be[v]) swap(u, v);
                for (auto &pai : gr[u]) {
                    int nxt = pai.first, cost = pai.second;
                    if (nxt != par[u]) continue ;
                    if (!cost) {
                        pai.second = c;
                        ret += cnt[u] * c;
                    }
                    dsu.unionSet(u, par[u]);
                    u = dsu.findSet(u);
                }
            }
        }

        ans = max(ans, ret);
    }

    printf("%lld", ans);

    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d %d", &n, &nRoad, &nNewRoad);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:56:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, c; scanf(" %d %d %d", &u, &v, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf(" %d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~~
toll.cpp:68:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf(" %d", &nPeople[i]);
                                  ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 257 ms 8572 KB Output is correct
8 Correct 293 ms 8512 KB Output is correct
9 Correct 290 ms 8484 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 257 ms 8572 KB Output is correct
8 Correct 293 ms 8512 KB Output is correct
9 Correct 290 ms 8484 KB Output is correct
10 Correct 2150 ms 8512 KB Output is correct
11 Execution timed out 2536 ms 8444 KB Time limit exceeded
12 Halted 0 ms 0 KB -