답안 #102502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102502 2019-03-25T12:09:07 Z alexpetrescu Designated Cities (JOI19_designated_cities) C++14
0 / 100
2000 ms 30096 KB
#include <cstdio>
#include <vector>
#include <algorithm>
#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], ind[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 h[a] > h[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 = 3; i <= e[0]; i++) {
        int best = 0;
        for (int j = 1; j <= n; j++) {
            if (luat[j]) {
                while (ind[j] < (int)candidat[j].size() && luat[candidat[j][ind[j]]])
                    ind[j]++;
                if (ind[j] < (int)candidat[j].size() && cost[candidat[j][ind[j]]] > cost[best])
                    best = candidat[j][ind[j]];
            }
        }
        if (best == 0)
            exit(1);
        ans[i] = ans[i - 1] - cost[best];
        while (luat[best] == 0) {
            luat[best] = 1;
            best = t[best];
        }
    }
}

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:138: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:142: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:155: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:159:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d", &x);
         ~~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 11 ms 9864 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Incorrect 10 ms 9856 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Execution timed out 2048 ms 30024 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 9728 KB Output is correct
2 Execution timed out 2071 ms 30096 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 11 ms 9864 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Incorrect 10 ms 9856 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Execution timed out 2048 ms 30024 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 11 ms 9864 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Incorrect 10 ms 9856 KB Output isn't correct
8 Halted 0 ms 0 KB -