oj.uz

Submission #102511

# Submission time Handle Problem Language Result Execution time Memory
102511 2019-03-25T13:02:15 Z alexpetrescu Designated Cities (JOI19_designated_cities) C++14
7 / 100
 583 ms 33296 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cassert>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define ll long long

#define MAXN 200009

struct myc {
    int x, y, z;
};
std::vector < int > candidat[MAXN];
std::vector < myc > g[MAXN];
ll ans[MAXN], sumaTuturor;
int e[MAXN], desteptu[MAXN], istetu[MAXN];
bool viz[MAXN], luat[MAXN], seen[MAXN];
ll sum[MAXN], calc[MAXN], h[MAXN], cost[MAXN];
int t[MAXN], cine[MAXN], perm[MAXN];
int A, B, C;

void dfs1(int x) {
    viz[x] = 1;
    for (auto &y : g[x]) {
        if (viz[y.x] == 0) {
            dfs1(y.x);
            sum[x] += sum[y.x] + y.z;
        }
    }
}

void dfs2(int x, ll dinSpate) {
    viz[x] = 1;
    calc[x] = sum[x] + dinSpate;
    ans[1] = std::min(ans[1], sumaTuturor - calc[x]);
    desteptu[x] = x;
    for (auto &y : g[x]) {
        if (viz[y.x] == 0) {
            h[y.x] = h[x] + y.y;
            dfs2(y.x, dinSpate + sum[x] - sum[y.x] - y.z + y.y);
            if (h[desteptu[y.x]] > h[desteptu[x]]) {
                istetu[x] = desteptu[x];
                desteptu[x] = desteptu[y.x];
            } else if (h[desteptu[y.x]] > h[istetu[x]])
                istetu[x] = desteptu[y.x];
        }
    }
    if (h[desteptu[x]] + h[istetu[x]] - h[x] + calc[x] > h[A] + h[B] - h[C] + calc[C])
        A = desteptu[x], B = istetu[x], C = x;
}

void dfs3(int x) {
    viz[x] = 1;
    bool frunza = 1;
    desteptu[x] = x;
    for (auto &y : g[x]) {
        if (viz[y.x] == 0) {
            frunza = 0;
            h[y.x] = h[x] + y.y;
            t[y.x] = x;
            dfs3(y.x);
            if (h[desteptu[y.x]] > h[desteptu[x]])
                desteptu[x] = desteptu[y.x];
            luat[x] |= luat[y.x];
            if (luat[y.x] == 0)
                ans[2] += y.y;
        }
    }
    if(frunza)
        e[++e[0]] = x;
}

bool cmp(const int &a, const int &b) {
    return cost[a] > cost[b];
}

inline void solve(int n) {
    int rad = 0;
    for (int i = 1; i <= n; i++)
        if ((int)g[i].size() != 1)
            rad = i;
    ans[1] = sumaTuturor;
    dfs1(rad);
    for (int i = 1; i <= n; i++)
        viz[i] = 0;
    h[0] = cost[0] = -1000000000000000000LL;
    dfs2(rad, 0);
    for (int i = 1; i <= n; i++)
        viz[i] = 0;
    luat[A] = luat[B] = 1;
    h[C] = 0;
    dfs3(C);

    for (int i = 1; i <= n; i++)
        for (auto &x : g[i])
            if (t[x.x] == i)
                cost[x.x] = h[desteptu[x.x]] - h[i], cine[x.x] = desteptu[x.x];

    for (int i = 1; i <= n; i++)
        perm[i] = i;
    std::sort(perm + 1, perm + n + 1, cmp);

    int poz = 1;
    for (int i = 3; i <= e[0]; i++) {
        while (luat[perm[poz]])
            poz++;
        ans[i] = ans[i - 1] - cost[perm[poz]];
        int x = cine[perm[poz]];
        while (luat[x] == 0) {
            luat[x] = 1;
            x = t[x];
        }
    }
}

int main() {
    int n;
    fscanf(fin, "%d", &n);

    for (int i = 1; i < n; i++) {
        int x, y, z, t;
        fscanf(fin, "%d%d%d%d", &x, &y, &z, &t);

        g[x].push_back({y, z, t});
        g[y].push_back({x, t, z});

        sumaTuturor += z + t;
        ans[1] = std::min(z, t);
    }

    if (n > 2)
        solve(n);

    int q;
    fscanf(fin, "%d", &q);

    for (; q; q--) {
        int x;
        fscanf(fin, "%d", &x);

        assert(x != 2);

        fprintf(fout, "%lld\n", ans[x]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:124:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d", &n);
     ~~~~~~^~~~~~~~~~~~~~~
designated_cities.cpp:128:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d%d%d%d", &x, &y, &z, &t);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:141:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d", &q);
     ~~~~~~^~~~~~~~~~~~~~~
designated_cities.cpp:145:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d", &x);
         ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 19200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9700 KB Output is correct
2 Correct 543 ms 29516 KB Output is correct
3 Correct 576 ms 31736 KB Output is correct
4 Correct 512 ms 29696 KB Output is correct
5 Correct 518 ms 29552 KB Output is correct
6 Correct 518 ms 30404 KB Output is correct
7 Correct 422 ms 29864 KB Output is correct
8 Correct 583 ms 33296 KB Output is correct
9 Correct 318 ms 28948 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 19200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9700 KB Output is correct
2 Correct 543 ms 29516 KB Output is correct
3 Correct 576 ms 31736 KB Output is correct
4 Correct 512 ms 29696 KB Output is correct
5 Correct 518 ms 29552 KB Output is correct
6 Correct 518 ms 30404 KB Output is correct
7 Correct 422 ms 29864 KB Output is correct
8 Correct 583 ms 33296 KB Output is correct
9 Correct 318 ms 28948 KB Output is correct
10 Runtime error 24 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 19200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -