oj.uz

Submission #102492

# Submission time Handle Problem Language Result Execution time Memory
102492 2019-03-25T11:14:58 Z alexpetrescu Designated Cities (JOI19_designated_cities) C++14
7 / 100
 481 ms 26104 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

//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 < myc > g[MAXN];
ll ans[MAXN], sumaTuturor;
int e[MAXN], desteptu[MAXN], istetu[MAXN];
bool viz[MAXN], luat[MAXN];
ll sum[MAXN], calc[MAXN], h[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;
    for (auto &y : g[x]) {
        if (viz[y.x] == 0) {
            frunza = 0;
            h[y.x] = h[x] + y.y;
            dfs3(y.x);
            luat[x] |= luat[y.x];
            if (luat[y.x] == 0)
                ans[2] += y.y;
        }
    }
    if(frunza)
        e[++e[0]] = x;
}

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

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:89: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:93: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:106: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:110: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 Correct 7 ms 4992 KB Output is correct
2 Incorrect 7 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 423 ms 20368 KB Output is correct
3 Correct 451 ms 25672 KB Output is correct
4 Correct 384 ms 20312 KB Output is correct
5 Correct 477 ms 20116 KB Output is correct
6 Correct 435 ms 21408 KB Output is correct
7 Correct 391 ms 20180 KB Output is correct
8 Correct 455 ms 26104 KB Output is correct
9 Correct 276 ms 18596 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Incorrect 481 ms 20312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 423 ms 20368 KB Output is correct
3 Correct 451 ms 25672 KB Output is correct
4 Correct 384 ms 20312 KB Output is correct
5 Correct 477 ms 20116 KB Output is correct
6 Correct 435 ms 21408 KB Output is correct
7 Correct 391 ms 20180 KB Output is correct
8 Correct 455 ms 26104 KB Output is correct
9 Correct 276 ms 18596 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct
11 Incorrect 481 ms 20312 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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