oj.uz

Submission #73874

# Submission time Handle Problem Language Result Execution time Memory
73874 2018-08-29T07:49:50 Z 강태규(#2274) Toll (APIO13_toll) C++11
100 / 100
 2453 ms 44908 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m, k;

struct _es {
    int x, y, c;
    bool operator<(const _es &p) const {
        return c < p.c;
    }
    void scan(int t) {
        scanf("%d%d", &x, &y);
        if (t) scanf("%d", &c);
    }
} es[300020];

int uf[100001];
int find(int x) {
    if (uf[x]) return uf[x] = find(uf[x]);
    return x;
}

int merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return 0;
    uf[y] = x;
    return 1;
}

int ps[100001];
int idx[100001];
llong cnt[25];

const int inf = 1e8;
vector<int> edge[25];
int par[25];
int dep[25];
int col[25];
llong sz[25];
void dfs(int x, int p) {
    par[x] = p;
    dep[x] = dep[p] + 1;
    col[x] = inf;
    sz[x] = cnt[x];
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs(i, x);
        sz[x] += sz[i];
    }
}

llong solve(int mask, const vector<_es> &cs) {
    vector<_es> ks;
    for (int i = 1; i <= n; ++i) {
        edge[i].clear();
        uf[i] = 0;
    }
    for (int i = 0; i < k; ++i) if ((mask >> i) & 1) ks.push_back(es[i]);
    for (_es i : ks) if (merge(i.x, i.y) == 0) return 0;
    for (_es i : ks) {
        edge[i.x].push_back(i.y);
        edge[i.y].push_back(i.x);
    }
    for (_es i : cs) {
        if (merge(i.x, i.y)) {
            edge[i.x].push_back(i.y);
            edge[i.y].push_back(i.x);
        }
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) uf[i] = 0;
    for (_es i : cs) {
        int x = find(i.x), y = find(i.y), c = i.c;
        while (x != y) {
            if (dep[x] < dep[y]) swap(x, y);
            col[x] = c;
            x = uf[x] = find(par[x]);
        }
    }
    llong ret = 0;
    for (_es i : ks) {
        int x = i.x, y = i.y;
        if (dep[x] < dep[y]) swap(x, y);
        ret += col[x] * sz[x];
    }
    return ret;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; ++i) es[i + k].scan(1);
    for (int i = 0; i < k; ++i) es[i].scan(0);
    for (int i = 1; i <= n; ++i) scanf("%d", ps + i);
    sort(es + k, es + (m + k));
    vector<int> useEdge;
    for (int i = 0; i < k; ++i) merge(es[i].x, es[i].y);
    for (int i = 0; i < m; ++i) if (merge(es[i + k].x, es[i + k].y))
        useEdge.push_back(i + k);
    for (int i = 1; i <= n; ++i) uf[i] = 0;
    for (int i : useEdge) merge(es[i].x, es[i].y);
    int cp = 0;
    for (int i = 1; i <= n; ++i) {
        if (idx[find(i)]) continue;
        idx[find(i)] = ++cp;
    }
    for (int i = 1; i <= n; ++i) idx[i] = idx[find(i)];
    for (int i = 1; i <= n; ++i) cnt[idx[find(i)]] += ps[i];
    vector<_es> needEdge;
    for (int i = 0; i < m; ++i) if (merge(es[i + k].x, es[i + k].y))
        needEdge.push_back({ idx[es[i + k].x], idx[es[i + k].y], es[i + k].c });
    for (int i = 0; i < k; ++i) {
        es[i].x = idx[es[i].x];
        es[i].y = idx[es[i].y];
    }
    n = cp;
    llong ans = 0;
    for (int i = 1; i < (1 << k); ++i) ans = max(ans, solve(i, needEdge));
    printf("%lld\n", ans);
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:110: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", ps + i);
                                  ~~~~~^~~~~~~~~~~~~~
toll.cpp: In member function 'void _es::scan(int)':
toll.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:30:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         if (t) scanf("%d", &c);
                ~~~~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 4 ms 564 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 4 ms 564 KB Output is correct
5 Correct 7 ms 748 KB Output is correct
6 Correct 9 ms 816 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 4 ms 564 KB Output is correct
5 Correct 7 ms 748 KB Output is correct
6 Correct 9 ms 816 KB Output is correct
7 Correct 288 ms 12508 KB Output is correct
8 Correct 309 ms 19060 KB Output is correct
9 Correct 303 ms 25460 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 4 ms 564 KB Output is correct
5 Correct 7 ms 748 KB Output is correct
6 Correct 9 ms 816 KB Output is correct
7 Correct 288 ms 12508 KB Output is correct
8 Correct 309 ms 19060 KB Output is correct
9 Correct 303 ms 25460 KB Output is correct
10 Correct 1760 ms 32028 KB Output is correct
11 Correct 2162 ms 38424 KB Output is correct
12 Correct 2453 ms 44908 KB Output is correct