oj.uz

Submission #73878

# Submission time Handle Problem Language Result Execution time Memory
73878 2018-08-29T07:58:35 Z 강태규(#2274) Toll (APIO13_toll) C++11
100 / 100
 2064 ms 5788 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;

char nextChar() {
    const int sz = 1 << 12;
    static char buf[sz];
    static int seek = sz;
    if (seek == sz) {
        fread(buf, 1, sz, stdin);
        seek = 0;
    }
    return buf[seek++];
}

int nextInt() {
    char c;
    while ((c = nextChar()) < '0' || '9' < c);
    int ret = c - '0';
    while ('0' <= (c = nextChar()) && c <= '9') {
        ret = (ret << 3) + (ret << 1);
        ret += c - '0';
    }
    return ret;
}

struct _es {
    int x, y, c;
    bool operator<(const _es &p) const {
        return c < p.c;
    }
    void scan(int t) {
        x = nextInt(); y = nextInt();
        if (t) c = nextInt();
    }
} 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() {
    n = nextInt(); m = nextInt(); k = nextInt();
    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) ps[i] = nextInt();
    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 'char nextChar()':
toll.cpp:28:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buf, 1, sz, stdin);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 5 ms 692 KB Output is correct
4 Correct 4 ms 692 KB Output is correct
5 Correct 5 ms 692 KB Output is correct
6 Correct 4 ms 692 KB Output is correct
7 Correct 146 ms 5724 KB Output is correct
8 Correct 143 ms 5788 KB Output is correct
9 Correct 141 ms 5788 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 5 ms 692 KB Output is correct
4 Correct 4 ms 692 KB Output is correct
5 Correct 5 ms 692 KB Output is correct
6 Correct 4 ms 692 KB Output is correct
7 Correct 146 ms 5724 KB Output is correct
8 Correct 143 ms 5788 KB Output is correct
9 Correct 141 ms 5788 KB Output is correct
10 Correct 1644 ms 5788 KB Output is correct
11 Correct 2064 ms 5788 KB Output is correct
12 Correct 2001 ms 5788 KB Output is correct