oj.uz

답안 #102507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102507 2019-03-25T12:38:01 Z alexpetrescu Designated Cities (JOI19_designated_cities) C++14
33 / 100
 697 ms 39072 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdlib>

//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];
}

void dfs4(int x) {
    viz[x] = 1;
    for (auto &y : g[x]) {
        if (viz[y.x] == 0) {
            if (luat[y.x] == 0 && seen[desteptu[y.x]] == 0) {
                seen[desteptu[y.x]] = 1;
                cost[desteptu[y.x]] = h[desteptu[y.x]] - h[x];
                candidat[x].push_back(desteptu[y.x]);
            }
            dfs4(y.x);
        }
    }
    std::sort(candidat[x].begin(), candidat[x].end(), cmp);
}

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++)
        viz[i] = 0;
    dfs4(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[cine[perm[poz]]])
            poz++;
        ans[i] = ans[i - 1] - cost[perm[poz]];
        int best = cine[perm[poz]];
        while (luat[best] == 0) {
            luat[best] = 1;
            best = t[best];
        }
    }
    assert(ans[e[0]] == 0);
}

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);

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

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

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:142: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:146: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:159: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:163: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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 12 ms 9772 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 11 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Incorrect 11 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 641 ms 31352 KB Output is correct
3 Correct 675 ms 35240 KB Output is correct
4 Correct 646 ms 31492 KB Output is correct
5 Correct 623 ms 31280 KB Output is correct
6 Correct 666 ms 32960 KB Output is correct
7 Correct 563 ms 31140 KB Output is correct
8 Correct 687 ms 38136 KB Output is correct
9 Correct 491 ms 31012 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 602 ms 31312 KB Output is correct
3 Correct 674 ms 34668 KB Output is correct
4 Correct 661 ms 31572 KB Output is correct
5 Correct 640 ms 31324 KB Output is correct
6 Correct 583 ms 32972 KB Output is correct
7 Correct 411 ms 32812 KB Output is correct
8 Correct 656 ms 39072 KB Output is correct
9 Correct 416 ms 30884 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 12 ms 9772 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 11 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Incorrect 11 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 641 ms 31352 KB Output is correct
3 Correct 675 ms 35240 KB Output is correct
4 Correct 646 ms 31492 KB Output is correct
5 Correct 623 ms 31280 KB Output is correct
6 Correct 666 ms 32960 KB Output is correct
7 Correct 563 ms 31140 KB Output is correct
8 Correct 687 ms 38136 KB Output is correct
9 Correct 491 ms 31012 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 602 ms 31312 KB Output is correct
12 Correct 674 ms 34668 KB Output is correct
13 Correct 661 ms 31572 KB Output is correct
14 Correct 640 ms 31324 KB Output is correct
15 Correct 583 ms 32972 KB Output is correct
16 Correct 411 ms 32812 KB Output is correct
17 Correct 656 ms 39072 KB Output is correct
18 Correct 416 ms 30884 KB Output is correct
19 Correct 11 ms 9728 KB Output is correct
20 Correct 595 ms 31380 KB Output is correct
21 Correct 624 ms 35444 KB Output is correct
22 Correct 580 ms 31452 KB Output is correct
23 Correct 553 ms 31480 KB Output is correct
24 Correct 589 ms 31436 KB Output is correct
25 Correct 600 ms 31304 KB Output is correct
26 Correct 614 ms 31480 KB Output is correct
27 Correct 640 ms 31196 KB Output is correct
28 Correct 570 ms 33032 KB Output is correct
29 Correct 629 ms 30864 KB Output is correct
30 Correct 575 ms 31792 KB Output is correct
31 Correct 492 ms 31476 KB Output is correct
32 Correct 697 ms 38236 KB Output is correct
33 Correct 467 ms 30996 KB Output is correct

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 12 ms 9772 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 11 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Incorrect 11 ms 9728 KB Output isn't correct
8 Halted 0 ms 0 KB -