답안 #46593 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46593	2018-04-21T16:21:22 Z	nickyrio	Construction of Highway (JOI18_construction)	C++17	100 / 100	570 ms	152164 KB

construction

//https://oj.uz/problem/view/JOI18_construction
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 100100
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

int n, u[N], v[N], p[N], d[N], c[N], nChild[N], head[N];
vector<int> e[N];

void dfs(int u) {
    nChild[u] = 1;
    for (int v : e[u]) {
        p[v] = u;
        d[v] = d[u] + 1;
        dfs(v);
        nChild[u] += nChild[v];
    }
}

void hld(int u) {
    if (head[u] == 0) head[u] = u;
    int mx = 0, special = -1;
    for (int v : e[u]) {
        if (mx < nChild[v]) {
            special = v; mx = nChild[v];
        }
    }
    for (int v : e[u]) {
        if (v == special) head[v] = head[u];
        else head[v] = v;
        hld(v);
    }
}

long long BIT[N];
long long GetBIT(int u) {
    long long ans = 0;
    for (; u > 0; u -= u & -u) ans += BIT[u];
    return ans;
}

void UpBIT(int u, long long val) {
    for (; u <= n; u += u & -u) BIT[u] += val;
}

struct Data {
    int depth, val, cnt;
};
deque<Data> deq[N];
long long Query(int u) {
    long long ans = 0;
    vector<pp> history;

    while (u) {
        int id = head[u];
        vector<Data> temp;
        int depth = d[u];
        while (!deq[id].empty() && deq[id].back().depth < depth) {
            temp.push_back(deq[id].back());
            deq[id].pop_back();
        }
        if (!deq[id].empty()) {
            Data t = deq[id].back(); deq[id].pop_back();
            int newCnt = t.depth - depth;
            t.cnt -= newCnt;
            temp.push_back(t);
            t.cnt = newCnt;
            if (t.cnt) deq[id].push_back(t);
        }
        while (!temp.empty()) {
            Data t = temp.back(); temp.pop_back();
            ans += 1ll * t.cnt * GetBIT(t.val - 1);
            UpBIT(t.val, t.cnt);
            history.push_back(pp(t.val, t.cnt));
        }
        u = p[head[u]];
    }
    for (pp x : history) UpBIT(x.first, -x.second);
    return ans;
}

void Update(int u) {
    Data x;
    x.val = c[u];
    while (u) {
        int id = head[u];
        x.depth = d[u];
        x.cnt = d[u] - d[p[head[u]]];
       // DEBUG(deq[id].size());
        deq[id].push_back(x);
        u = p[head[u]];
    }
}

int ranking[N];

int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    cin >> n;
    FOR(i, 1, n) cin >> c[i];
    FOR(i, 1, n) ranking[i] = c[i];
    sort(ranking + 1, ranking + n + 1);
    FOR(i, 1, n) {
        c[i] = lower_bound(ranking + 1, ranking + n + 1, c[i]) - ranking;
    }
    FOR(i, 2, n) {
        cin >> u[i] >> v[i];
        e[u[i]].push_back(v[i]);
    }
    d[1] = 1;
    dfs(1);
    hld(1);
    FOR(i, 2, n) {
        cout << Query(u[i]) << '\n';
        Update(v[i]);
    }
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	68600 KB	Output is correct
2	Correct	64 ms	68600 KB	Output is correct
3	Correct	62 ms	68804 KB	Output is correct
4	Correct	63 ms	68804 KB	Output is correct
5	Correct	70 ms	68808 KB	Output is correct
6	Correct	65 ms	68880 KB	Output is correct
7	Correct	63 ms	69036 KB	Output is correct
8	Correct	62 ms	69036 KB	Output is correct
9	Correct	61 ms	69056 KB	Output is correct
10	Correct	62 ms	69084 KB	Output is correct
11	Correct	64 ms	69112 KB	Output is correct
12	Correct	62 ms	69284 KB	Output is correct
13	Correct	61 ms	69284 KB	Output is correct
14	Correct	61 ms	69284 KB	Output is correct
15	Correct	62 ms	69284 KB	Output is correct
16	Correct	60 ms	69284 KB	Output is correct
17	Correct	63 ms	69284 KB	Output is correct
18	Correct	61 ms	69284 KB	Output is correct
19	Correct	64 ms	69284 KB	Output is correct
20	Correct	69 ms	69284 KB	Output is correct
21	Correct	63 ms	69284 KB	Output is correct
22	Correct	63 ms	69284 KB	Output is correct
23	Correct	62 ms	69284 KB	Output is correct
24	Correct	61 ms	69284 KB	Output is correct
25	Correct	62 ms	69284 KB	Output is correct
26	Correct	62 ms	69284 KB	Output is correct
27	Correct	61 ms	69284 KB	Output is correct
28	Correct	62 ms	69292 KB	Output is correct
29	Correct	62 ms	69404 KB	Output is correct
30	Correct	62 ms	69404 KB	Output is correct
31	Correct	64 ms	69404 KB	Output is correct
32	Correct	71 ms	69404 KB	Output is correct
33	Correct	63 ms	69420 KB	Output is correct
34	Correct	62 ms	69432 KB	Output is correct
35	Correct	73 ms	69432 KB	Output is correct
36	Correct	64 ms	69484 KB	Output is correct
37	Correct	63 ms	69484 KB	Output is correct
38	Correct	62 ms	69484 KB	Output is correct
39	Correct	66 ms	69512 KB	Output is correct
40	Correct	64 ms	69512 KB	Output is correct
41	Correct	61 ms	69512 KB	Output is correct
42	Correct	62 ms	69512 KB	Output is correct
43	Correct	64 ms	69544 KB	Output is correct
44	Correct	62 ms	69544 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	68600 KB	Output is correct
2	Correct	64 ms	68600 KB	Output is correct
3	Correct	62 ms	68804 KB	Output is correct
4	Correct	63 ms	68804 KB	Output is correct
5	Correct	70 ms	68808 KB	Output is correct
6	Correct	65 ms	68880 KB	Output is correct
7	Correct	63 ms	69036 KB	Output is correct
8	Correct	62 ms	69036 KB	Output is correct
9	Correct	61 ms	69056 KB	Output is correct
10	Correct	62 ms	69084 KB	Output is correct
11	Correct	64 ms	69112 KB	Output is correct
12	Correct	62 ms	69284 KB	Output is correct
13	Correct	61 ms	69284 KB	Output is correct
14	Correct	61 ms	69284 KB	Output is correct
15	Correct	62 ms	69284 KB	Output is correct
16	Correct	60 ms	69284 KB	Output is correct
17	Correct	63 ms	69284 KB	Output is correct
18	Correct	61 ms	69284 KB	Output is correct
19	Correct	64 ms	69284 KB	Output is correct
20	Correct	69 ms	69284 KB	Output is correct
21	Correct	63 ms	69284 KB	Output is correct
22	Correct	63 ms	69284 KB	Output is correct
23	Correct	62 ms	69284 KB	Output is correct
24	Correct	61 ms	69284 KB	Output is correct
25	Correct	62 ms	69284 KB	Output is correct
26	Correct	62 ms	69284 KB	Output is correct
27	Correct	61 ms	69284 KB	Output is correct
28	Correct	62 ms	69292 KB	Output is correct
29	Correct	62 ms	69404 KB	Output is correct
30	Correct	62 ms	69404 KB	Output is correct
31	Correct	64 ms	69404 KB	Output is correct
32	Correct	71 ms	69404 KB	Output is correct
33	Correct	63 ms	69420 KB	Output is correct
34	Correct	62 ms	69432 KB	Output is correct
35	Correct	73 ms	69432 KB	Output is correct
36	Correct	64 ms	69484 KB	Output is correct
37	Correct	63 ms	69484 KB	Output is correct
38	Correct	62 ms	69484 KB	Output is correct
39	Correct	66 ms	69512 KB	Output is correct
40	Correct	64 ms	69512 KB	Output is correct
41	Correct	61 ms	69512 KB	Output is correct
42	Correct	62 ms	69512 KB	Output is correct
43	Correct	64 ms	69544 KB	Output is correct
44	Correct	62 ms	69544 KB	Output is correct
45	Correct	63 ms	69596 KB	Output is correct
46	Correct	68 ms	69740 KB	Output is correct
47	Correct	72 ms	69836 KB	Output is correct
48	Correct	69 ms	69892 KB	Output is correct
49	Correct	65 ms	70224 KB	Output is correct
50	Correct	66 ms	70300 KB	Output is correct
51	Correct	66 ms	70376 KB	Output is correct
52	Correct	70 ms	70456 KB	Output is correct
53	Correct	76 ms	70456 KB	Output is correct
54	Correct	72 ms	70512 KB	Output is correct
55	Correct	73 ms	70532 KB	Output is correct
56	Correct	66 ms	70656 KB	Output is correct
57	Correct	81 ms	70656 KB	Output is correct
58	Correct	73 ms	70656 KB	Output is correct
59	Correct	80 ms	70852 KB	Output is correct
60	Correct	75 ms	70852 KB	Output is correct
61	Correct	121 ms	70948 KB	Output is correct
62	Correct	67 ms	71044 KB	Output is correct
63	Correct	65 ms	71124 KB	Output is correct
64	Correct	69 ms	71124 KB	Output is correct
65	Correct	74 ms	71124 KB	Output is correct
66	Correct	72 ms	71164 KB	Output is correct
67	Correct	68 ms	71216 KB	Output is correct
68	Correct	64 ms	71608 KB	Output is correct
69	Correct	72 ms	71608 KB	Output is correct
70	Correct	79 ms	71608 KB	Output is correct
71	Correct	69 ms	71608 KB	Output is correct
72	Correct	72 ms	71608 KB	Output is correct
73	Correct	72 ms	71608 KB	Output is correct
74	Correct	84 ms	71608 KB	Output is correct
75	Correct	66 ms	71628 KB	Output is correct
76	Correct	67 ms	71692 KB	Output is correct
77	Correct	67 ms	71756 KB	Output is correct
78	Correct	66 ms	71820 KB	Output is correct
79	Correct	82 ms	71868 KB	Output is correct
80	Correct	65 ms	71920 KB	Output is correct
81	Correct	83 ms	72092 KB	Output is correct
82	Correct	70 ms	72092 KB	Output is correct
83	Correct	72 ms	72112 KB	Output is correct
84	Correct	68 ms	72172 KB	Output is correct
85	Correct	66 ms	72240 KB	Output is correct
86	Correct	78 ms	72396 KB	Output is correct

Subtask #3
84.0 / 84.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	68600 KB	Output is correct
2	Correct	64 ms	68600 KB	Output is correct
3	Correct	62 ms	68804 KB	Output is correct
4	Correct	63 ms	68804 KB	Output is correct
5	Correct	70 ms	68808 KB	Output is correct
6	Correct	65 ms	68880 KB	Output is correct
7	Correct	63 ms	69036 KB	Output is correct
8	Correct	62 ms	69036 KB	Output is correct
9	Correct	61 ms	69056 KB	Output is correct
10	Correct	62 ms	69084 KB	Output is correct
11	Correct	64 ms	69112 KB	Output is correct
12	Correct	62 ms	69284 KB	Output is correct
13	Correct	61 ms	69284 KB	Output is correct
14	Correct	61 ms	69284 KB	Output is correct
15	Correct	62 ms	69284 KB	Output is correct
16	Correct	60 ms	69284 KB	Output is correct
17	Correct	63 ms	69284 KB	Output is correct
18	Correct	61 ms	69284 KB	Output is correct
19	Correct	64 ms	69284 KB	Output is correct
20	Correct	69 ms	69284 KB	Output is correct
21	Correct	63 ms	69284 KB	Output is correct
22	Correct	63 ms	69284 KB	Output is correct
23	Correct	62 ms	69284 KB	Output is correct
24	Correct	61 ms	69284 KB	Output is correct
25	Correct	62 ms	69284 KB	Output is correct
26	Correct	62 ms	69284 KB	Output is correct
27	Correct	61 ms	69284 KB	Output is correct
28	Correct	62 ms	69292 KB	Output is correct
29	Correct	62 ms	69404 KB	Output is correct
30	Correct	62 ms	69404 KB	Output is correct
31	Correct	64 ms	69404 KB	Output is correct
32	Correct	71 ms	69404 KB	Output is correct
33	Correct	63 ms	69420 KB	Output is correct
34	Correct	62 ms	69432 KB	Output is correct
35	Correct	73 ms	69432 KB	Output is correct
36	Correct	64 ms	69484 KB	Output is correct
37	Correct	63 ms	69484 KB	Output is correct
38	Correct	62 ms	69484 KB	Output is correct
39	Correct	66 ms	69512 KB	Output is correct
40	Correct	64 ms	69512 KB	Output is correct
41	Correct	61 ms	69512 KB	Output is correct
42	Correct	62 ms	69512 KB	Output is correct
43	Correct	64 ms	69544 KB	Output is correct
44	Correct	62 ms	69544 KB	Output is correct
45	Correct	63 ms	69596 KB	Output is correct
46	Correct	68 ms	69740 KB	Output is correct
47	Correct	72 ms	69836 KB	Output is correct
48	Correct	69 ms	69892 KB	Output is correct
49	Correct	65 ms	70224 KB	Output is correct
50	Correct	66 ms	70300 KB	Output is correct
51	Correct	66 ms	70376 KB	Output is correct
52	Correct	70 ms	70456 KB	Output is correct
53	Correct	76 ms	70456 KB	Output is correct
54	Correct	72 ms	70512 KB	Output is correct
55	Correct	73 ms	70532 KB	Output is correct
56	Correct	66 ms	70656 KB	Output is correct
57	Correct	81 ms	70656 KB	Output is correct
58	Correct	73 ms	70656 KB	Output is correct
59	Correct	80 ms	70852 KB	Output is correct
60	Correct	75 ms	70852 KB	Output is correct
61	Correct	121 ms	70948 KB	Output is correct
62	Correct	67 ms	71044 KB	Output is correct
63	Correct	65 ms	71124 KB	Output is correct
64	Correct	69 ms	71124 KB	Output is correct
65	Correct	74 ms	71124 KB	Output is correct
66	Correct	72 ms	71164 KB	Output is correct
67	Correct	68 ms	71216 KB	Output is correct
68	Correct	64 ms	71608 KB	Output is correct
69	Correct	72 ms	71608 KB	Output is correct
70	Correct	79 ms	71608 KB	Output is correct
71	Correct	69 ms	71608 KB	Output is correct
72	Correct	72 ms	71608 KB	Output is correct
73	Correct	72 ms	71608 KB	Output is correct
74	Correct	84 ms	71608 KB	Output is correct
75	Correct	66 ms	71628 KB	Output is correct
76	Correct	67 ms	71692 KB	Output is correct
77	Correct	67 ms	71756 KB	Output is correct
78	Correct	66 ms	71820 KB	Output is correct
79	Correct	82 ms	71868 KB	Output is correct
80	Correct	65 ms	71920 KB	Output is correct
81	Correct	83 ms	72092 KB	Output is correct
82	Correct	70 ms	72092 KB	Output is correct
83	Correct	72 ms	72112 KB	Output is correct
84	Correct	68 ms	72172 KB	Output is correct
85	Correct	66 ms	72240 KB	Output is correct
86	Correct	78 ms	72396 KB	Output is correct
87	Correct	83 ms	72828 KB	Output is correct
88	Correct	136 ms	74812 KB	Output is correct
89	Correct	354 ms	80700 KB	Output is correct
90	Correct	347 ms	82812 KB	Output is correct
91	Correct	339 ms	85052 KB	Output is correct
92	Correct	196 ms	93324 KB	Output is correct
93	Correct	213 ms	95268 KB	Output is correct
94	Correct	197 ms	97528 KB	Output is correct
95	Correct	208 ms	97528 KB	Output is correct
96	Correct	211 ms	99164 KB	Output is correct
97	Correct	211 ms	101168 KB	Output is correct
98	Correct	218 ms	103404 KB	Output is correct
99	Correct	199 ms	103976 KB	Output is correct
100	Correct	513 ms	103976 KB	Output is correct
101	Correct	570 ms	105960 KB	Output is correct
102	Correct	533 ms	107980 KB	Output is correct
103	Correct	543 ms	110148 KB	Output is correct
104	Correct	208 ms	114096 KB	Output is correct
105	Correct	211 ms	116164 KB	Output is correct
106	Correct	228 ms	118268 KB	Output is correct
107	Correct	308 ms	118268 KB	Output is correct
108	Correct	328 ms	118528 KB	Output is correct
109	Correct	365 ms	120636 KB	Output is correct
110	Correct	176 ms	128084 KB	Output is correct
111	Correct	198 ms	128084 KB	Output is correct
112	Correct	215 ms	129156 KB	Output is correct
113	Correct	190 ms	129260 KB	Output is correct
114	Correct	488 ms	129260 KB	Output is correct
115	Correct	544 ms	130660 KB	Output is correct
116	Correct	210 ms	133876 KB	Output is correct
117	Correct	231 ms	134656 KB	Output is correct
118	Correct	263 ms	135868 KB	Output is correct
119	Correct	215 ms	137500 KB	Output is correct
120	Correct	205 ms	139700 KB	Output is correct
121	Correct	201 ms	140732 KB	Output is correct
122	Correct	203 ms	142112 KB	Output is correct
123	Correct	224 ms	144596 KB	Output is correct
124	Correct	230 ms	145956 KB	Output is correct
125	Correct	219 ms	147680 KB	Output is correct
126	Correct	206 ms	149668 KB	Output is correct
127	Correct	210 ms	150828 KB	Output is correct
128	Correct	207 ms	152164 KB	Output is correct

답안 #46593

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 9.0 / 9.0

Subtask #3 84.0 / 84.0

Subtask #1
7.0 / 7.0

Subtask #2
9.0 / 9.0

Subtask #3
84.0 / 84.0