oj.uz

Submission #131933

# Submission time Handle Problem Language Result Execution time Memory
131933 2019-07-18T04:59:53 Z 송준혁(#3192) Construction of Highway (JOI18_construction) C++14
0 / 100
 6 ms 2812 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N;
int A[101010], B[101010], C[101010];
int L[101010], R[101010], P[101010], H[101010], num;
int Max[404040], BIT[101010], D[101010];
vector<int> adj[101010], comp;

void updMax(int id, int s, int e, int t, int v){
    if (e < t || t < s) return;
    if (s == e){
        Max[id] = v;
        return;
    }
    int mid = (s+e)/2;
    updMax(id*2, s, mid, t, v);
    updMax(id*2+1, mid+1, e, t, v);
    Max[id] = max(Max[id*2], Max[id*2+1]);
}

int RMQ(int id, int s, int e, int ts, int te){
    if (e < ts || te < s) return 0;
    if (ts <= s && e <= te) return Max[id];
    int mid = (s+e)/2;
    return max(RMQ(id*2, s, mid, ts, te), RMQ(id*2+1, mid+1, e, ts, te));
}

void updBIT(int t, int v){
    while (t<=N){
        BIT[t] += v;
        t += t & -t;
    }
}

int read(int t){
    int ret = 0;
    while (t){
        ret += BIT[t];
        t -= t & -t;
    }
    return ret;
}

void dfs(int u, int p){
    L[u] = ++num, P[u] = p;
    for (int v : adj[u]){
        if (v == p) continue;
        D[v] = D[u] + 1;
        dfs(v, u);
    }
    R[u] = num;
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++){
        scanf("%d", &C[i]);
        comp.push_back(C[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (int i=1; i<=N; i++) C[i] = lower_bound(comp.begin(), comp.end(), C[i])-comp.begin()+1;
    for (int i=2; i<=N; i++){
        scanf("%d %d", &A[i], &B[i]);
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    D[1] = 1, B[1] = 1;
    dfs(1, 0);
    updMax(1, 1, N, L[1], 1);
    for (int i=2; i<=N; i++){
        int u = A[i];
        LL ans = 0;
        vector<pii> E;
        while (u != 0){
            int v = B[RMQ(1, 1, N, L[u], R[u])];
            ans += ((LL)(D[u]-D[H[v]]) * read(C[v]));
            updBIT(C[v], D[u]-D[H[v]]);
            E.push_back(pii(C[v], D[u]-D[H[v]]));
            int t = u;
            u = H[v], H[v] = t;
        }
        for (pii t : E) updBIT(t.first, -t.second);
        printf("%lld\n", ans);
        updMax(1, 1, N, L[B[i]], i);
    }
    return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
construction.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &C[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &A[i], &B[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 4 ms 2812 KB Output is correct
13 Correct 6 ms 2808 KB Output is correct
14 Correct 4 ms 2808 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 5 ms 2808 KB Output is correct
17 Correct 5 ms 2808 KB Output is correct
18 Correct 5 ms 2808 KB Output is correct
19 Correct 6 ms 2808 KB Output is correct
20 Correct 5 ms 2808 KB Output is correct
21 Correct 5 ms 2808 KB Output is correct
22 Incorrect 5 ms 2808 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 4 ms 2812 KB Output is correct
13 Correct 6 ms 2808 KB Output is correct
14 Correct 4 ms 2808 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 5 ms 2808 KB Output is correct
17 Correct 5 ms 2808 KB Output is correct
18 Correct 5 ms 2808 KB Output is correct
19 Correct 6 ms 2808 KB Output is correct
20 Correct 5 ms 2808 KB Output is correct
21 Correct 5 ms 2808 KB Output is correct
22 Incorrect 5 ms 2808 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 4 ms 2812 KB Output is correct
13 Correct 6 ms 2808 KB Output is correct
14 Correct 4 ms 2808 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 5 ms 2808 KB Output is correct
17 Correct 5 ms 2808 KB Output is correct
18 Correct 5 ms 2808 KB Output is correct
19 Correct 6 ms 2808 KB Output is correct
20 Correct 5 ms 2808 KB Output is correct
21 Correct 5 ms 2808 KB Output is correct
22 Incorrect 5 ms 2808 KB Output isn't correct
23 Halted 0 ms 0 KB -