oj.uz

Submission #208926

# Submission time Handle Problem Language Result Execution time Memory
208926 2020-03-12T14:02:37 Z EntityIT Toll (APIO13_toll) C++14
100 / 100
 2404 ms 9616 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 } );
        }
    }

    Dsu com(iId);
    vector<Edge> tmp;
    for (const auto &i : staredRoad) {
      if (!com.sameSet(i.u, i.v) ) {
        tmp.emplace_back(i);
        com.unionSet(i.u, i.v);
      }
    }
    staredRoad = tmp;

    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 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 8 ms 500 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 242 ms 9464 KB Output is correct
8 Correct 257 ms 9592 KB Output is correct
9 Correct 253 ms 9592 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 8 ms 500 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 242 ms 9464 KB Output is correct
8 Correct 257 ms 9592 KB Output is correct
9 Correct 253 ms 9592 KB Output is correct
10 Correct 2005 ms 9616 KB Output is correct
11 Correct 2404 ms 9464 KB Output is correct
12 Correct 2345 ms 9592 KB Output is correct