oj.uz

Submission #37177

# Submission time Handle Problem Language Result Execution time Memory
37177 2017-12-22T09:16:24 Z DoanPhuDuc Toll (APIO13_toll) C++
16 / 100
 3 ms 37676 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef long long LL;
typedef pair <int, int> II;
typedef pair <LL, int> LLI;

const int N = 1e5 + 10;

int n, m, q;
int a[N], h[N], b[N], wei[N], par[N];
int p[N][25], f[N][25];

bool fre[N];

LL ans = 0;
LL c[N];

vector <II> pos[N];
vector <int> L;
set <II> adj[N];

map <int, bool> change[N];

struct DSU {
    int p[N];
    void Init() {
        memset(p, -1, sizeof p);
    }
    int Root(int u) {
        return p[u] < 0 ? u : p[u] = Root(p[u]);
    }
    bool Union(int u, int v) {
        u = Root(u); v = Root(v);
        if (u == v) return false;
        if (p[u] > p[v]) swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return true;
    }
} DSU;

struct Edge {
    int u, v, w;
    Edge () {}
    Edge (int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator < (const Edge &that) const {
        return w < that.w;
    }
} E[N];

void DFS(int u) {
    for (set <II> :: iterator it = adj[u].begin(); it != adj[u].end(); ++it) {
        int v = it -> first, w = it -> second;
        if (v == p[u][0]) continue;
        a[v] = w; h[v] = h[u] + 1;
        p[v][0] = u;
        f[v][0] = v;
        DFS(v);
    }
}

int InitLCA() {
    for (int j = 1; 1 << j <= n; ++j)
        FOR(i, 1, n) {
            p[i][j] = p[p[i][j - 1]][j - 1];
            int x = f[i][j - 1], y = f[p[i][j - 1]][j - 1];
            if (a[x] < a[y]) f[i][j] = y;
                else f[i][j] = x;
        }
}

II LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    int k = 0;
    FOD(i, 20, 0) if (h[u] - (1 << i) >= h[v]) {
        if (a[f[u][i]] > a[k]) k = f[u][i];
        u = p[u][i];
    }
    if (u == v) return II(u, k);
    FOD(i, 20, 0) if (p[u][i] != p[v][i]) {
        if (a[f[u][i]] > a[k]) k = f[u][i];
        if (a[f[v][i]] > a[k]) k = f[v][i];
        u = p[u][i];
        v = p[v][i];
    }
    if (a[f[u][0]] > a[k]) k = f[u][0];
    if (a[f[v][0]] > a[k]) k = f[v][0];
    return II(p[u][0], k);
}

void DP(int u) {
    c[u] = b[u];
    for (set <II> :: iterator it = adj[u].begin(); it != adj[u].end(); ++it) {
        int v = it -> first, w = it -> second;
        if (v == par[u]) continue;
        par[v] = u; wei[v] = w;
        if (change[u][v] == true) fre[v] = true;
        DP(v);
        c[u] += c[v];
    }
}

LL Compute() {
    FOR(i, 1, n) fre[i] = false;
    DP(1);
    LL ans = 0;
    FOR(i, 1, n) if (fre[i] == true) ans += (LL)wei[i] * c[i];
    return ans;
}

void Try(int i) {
    if (i >= L.size()) {
        ans = max(ans, Compute());
        return;
    }
    Try(i + 1);
    int pu = p[L[i]][0], pv = L[i];
    adj[pu].erase(II(pv, a[L[i]]));
    adj[pv].erase(II(pu, a[L[i]]));
    REP(k, 0, pos[L[i]].size()) {
        int u = pos[L[i]][k].first, v = pos[L[i]][k].second;
        adj[u].insert(II(v, a[L[i]]));
        adj[v].insert(II(u, a[L[i]]));
        change[u][v] = change[v][u] = true;
        Try(i + 1);
        change[u][v] = change[v][u] = false;
        adj[u].erase(II(v, a[L[i]]));
        adj[v].erase(II(u, a[L[i]]));
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d%d", &n, &m, &q);
    FOR(i, 1, m) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        E[i] = Edge(u, v, w);
    }
    sort(E + 1, E + m + 1);
    DSU.Init();
    FOR(i, 1, m) {
        int u = E[i].u, v = E[i].v, w = E[i].w;
        if (DSU.Union(u, v) == true) {
            adj[u].insert(II(v, w));
            adj[v].insert(II(u, w));
        }
    }
    DFS(1);
    InitLCA();
    FOR(i, 1, q) {
        int x, y; scanf("%d%d", &x, &y);
        II res = LCA(x, y);
        pos[res.second].push_back(II(x, y));
    }
    FOR(i, 1, n) scanf("%d", &b[i]);
    FOR(i, 1, n) if (pos[i].size()) L.push_back(i);
    Try(0);
    cout << ans;

    return 0;
}

Compilation message

toll.cpp: In function 'int InitLCA()':
toll.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
toll.cpp: In function 'void Try(int)':
toll.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i >= L.size()) {
           ^
toll.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
toll.cpp:130:5: note: in expansion of macro 'REP'
     REP(k, 0, pos[L[i]].size()) {
     ^
toll.cpp: In function 'int main()':
toll.cpp:147:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
                                ^
toll.cpp:149:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, w; scanf("%d%d%d", &u, &v, &w);
                                                 ^
toll.cpp:164:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d%d", &x, &y);
                                        ^
toll.cpp:168:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &b[i]);
                                    ^

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37676 KB Output is correct
2 Correct 3 ms 37676 KB Output is correct
3 Incorrect 0 ms 37676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37676 KB Output is correct
2 Correct 3 ms 37676 KB Output is correct
3 Incorrect 0 ms 37676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37676 KB Output is correct
2 Correct 3 ms 37676 KB Output is correct
3 Incorrect 0 ms 37676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37676 KB Output is correct
2 Correct 3 ms 37676 KB Output is correct
3 Incorrect 0 ms 37676 KB Output isn't correct
4 Halted 0 ms 0 KB -