답안 #87221 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87221	2018-11-30T03:02:19 Z	tieunhi	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	297 ms	149804 KB

election_campaign

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define mid (r + l)/2
#define N 100005
#define LN 19

using namespace std;

int n, numQ, tin[N], tout[N], tt, h[N], p[N][LN], dp[N];
vector<pair<pii, int> >q[N];
vector<int> a[N];

struct BIT
{
    int t[N];
    void upd(int x, int val)
    {
        for (; x < N; x += (x & -x)) t[x] += val;
    }
    void upd(int l, int r, int val)
    {
        upd(l, val);
        upd(r+1, -val);
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x -= (x & -x)) ans += t[x];
        return ans;
    }
}t;

void preDFS(int u)
{
    tin[u] = ++tt;
    for (auto v : a[u])
    {
        if (v == p[u][0]) continue;
        h[v] = h[u] + 1;
        p[v][0] = u;
        FOR(i, 1, LN-1) p[v][i] = p[p[v][i-1]][i-1];
        preDFS(v);
    }
    tout[u] = tt;
}
int LCA(int u, int v)
{
    if (h[u] > h[v]) swap(u, v);
    int delta = h[v] - h[u];
    FOR(i, 0, LN-1)
        if ((delta >> i) & 1) v = p[v][i];
    if (u == v) return u;
    FORD(i, LN-1, 0)
        if (p[u][i] != p[v][i])
        {
            u = p[u][i];
            v = p[v][i];
        }
    return p[u][0];
}
int DFS(int u)
{
    int cur = 0;
    for (auto v : a[u])
    {
        if (v == p[u][0]) continue;
        cur += DFS(v);
    }
    dp[u] = cur;
    for (auto z : q[u])
    {
        int uu = z.F.F;
        int vv = z.F.S;
        int ww = z.S;
        dp[u] = max(dp[u], ww + t.get(tin[uu]) + t.get(tin[vv]) + cur);
    }
    t.upd(tin[u], tout[u], cur - dp[u]);
    return dp[u];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n;
    FOR(i, 2, n)
    {
        int u, v; cin >> u >> v;
        a[u].PB(v);
        a[v].PB(u);
    }
    preDFS(1);
    cin >> numQ;
    FOR(i, 1, numQ)
    {
        int u, v, w; cin >> u >> v >> w;
        int lca = LCA(u, v);
        q[lca].PB(mp(mp(u, v), w));
    }
    cout <<DFS(1);
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5240 KB	Output is correct
2	Correct	7 ms	5360 KB	Output is correct
3	Correct	6 ms	5360 KB	Output is correct
4	Correct	7 ms	5480 KB	Output is correct
5	Correct	134 ms	19260 KB	Output is correct
6	Correct	67 ms	26616 KB	Output is correct
7	Correct	122 ms	26616 KB	Output is correct
8	Correct	108 ms	26616 KB	Output is correct
9	Correct	134 ms	26688 KB	Output is correct
10	Correct	113 ms	26688 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	26688 KB	Output is correct
2	Correct	6 ms	26688 KB	Output is correct
3	Correct	7 ms	26688 KB	Output is correct
4	Correct	135 ms	35724 KB	Output is correct
5	Correct	161 ms	38196 KB	Output is correct
6	Correct	148 ms	40696 KB	Output is correct
7	Correct	166 ms	43316 KB	Output is correct
8	Correct	138 ms	45588 KB	Output is correct
9	Correct	148 ms	48128 KB	Output is correct
10	Correct	162 ms	50600 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	26688 KB	Output is correct
2	Correct	6 ms	26688 KB	Output is correct
3	Correct	7 ms	26688 KB	Output is correct
4	Correct	135 ms	35724 KB	Output is correct
5	Correct	161 ms	38196 KB	Output is correct
6	Correct	148 ms	40696 KB	Output is correct
7	Correct	166 ms	43316 KB	Output is correct
8	Correct	138 ms	45588 KB	Output is correct
9	Correct	148 ms	48128 KB	Output is correct
10	Correct	162 ms	50600 KB	Output is correct
11	Correct	17 ms	50600 KB	Output is correct
12	Correct	159 ms	53620 KB	Output is correct
13	Correct	162 ms	56292 KB	Output is correct
14	Correct	131 ms	59028 KB	Output is correct
15	Correct	154 ms	61760 KB	Output is correct
16	Correct	149 ms	64552 KB	Output is correct
17	Correct	140 ms	67240 KB	Output is correct
18	Correct	152 ms	69988 KB	Output is correct
19	Correct	153 ms	72688 KB	Output is correct
20	Correct	182 ms	75836 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	206 ms	75836 KB	Output is correct
2	Correct	147 ms	80524 KB	Output is correct
3	Correct	297 ms	80524 KB	Output is correct
4	Correct	199 ms	80524 KB	Output is correct
5	Correct	229 ms	85076 KB	Output is correct
6	Correct	156 ms	85076 KB	Output is correct
7	Correct	275 ms	89600 KB	Output is correct
8	Correct	187 ms	89600 KB	Output is correct
9	Correct	217 ms	97792 KB	Output is correct
10	Correct	273 ms	97792 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5240 KB	Output is correct
2	Correct	7 ms	5360 KB	Output is correct
3	Correct	6 ms	5360 KB	Output is correct
4	Correct	7 ms	5480 KB	Output is correct
5	Correct	134 ms	19260 KB	Output is correct
6	Correct	67 ms	26616 KB	Output is correct
7	Correct	122 ms	26616 KB	Output is correct
8	Correct	108 ms	26616 KB	Output is correct
9	Correct	134 ms	26688 KB	Output is correct
10	Correct	113 ms	26688 KB	Output is correct
11	Correct	7 ms	97792 KB	Output is correct
12	Correct	7 ms	97792 KB	Output is correct
13	Correct	7 ms	97792 KB	Output is correct
14	Correct	9 ms	97792 KB	Output is correct
15	Correct	7 ms	97792 KB	Output is correct
16	Correct	10 ms	97792 KB	Output is correct
17	Correct	7 ms	97792 KB	Output is correct
18	Correct	7 ms	97792 KB	Output is correct
19	Correct	7 ms	97792 KB	Output is correct
20	Correct	7 ms	97792 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5240 KB	Output is correct
2	Correct	7 ms	5360 KB	Output is correct
3	Correct	6 ms	5360 KB	Output is correct
4	Correct	7 ms	5480 KB	Output is correct
5	Correct	134 ms	19260 KB	Output is correct
6	Correct	67 ms	26616 KB	Output is correct
7	Correct	122 ms	26616 KB	Output is correct
8	Correct	108 ms	26616 KB	Output is correct
9	Correct	134 ms	26688 KB	Output is correct
10	Correct	113 ms	26688 KB	Output is correct
11	Correct	6 ms	26688 KB	Output is correct
12	Correct	6 ms	26688 KB	Output is correct
13	Correct	7 ms	26688 KB	Output is correct
14	Correct	135 ms	35724 KB	Output is correct
15	Correct	161 ms	38196 KB	Output is correct
16	Correct	148 ms	40696 KB	Output is correct
17	Correct	166 ms	43316 KB	Output is correct
18	Correct	138 ms	45588 KB	Output is correct
19	Correct	148 ms	48128 KB	Output is correct
20	Correct	162 ms	50600 KB	Output is correct
21	Correct	17 ms	50600 KB	Output is correct
22	Correct	159 ms	53620 KB	Output is correct
23	Correct	162 ms	56292 KB	Output is correct
24	Correct	131 ms	59028 KB	Output is correct
25	Correct	154 ms	61760 KB	Output is correct
26	Correct	149 ms	64552 KB	Output is correct
27	Correct	140 ms	67240 KB	Output is correct
28	Correct	152 ms	69988 KB	Output is correct
29	Correct	153 ms	72688 KB	Output is correct
30	Correct	182 ms	75836 KB	Output is correct
31	Correct	206 ms	75836 KB	Output is correct
32	Correct	147 ms	80524 KB	Output is correct
33	Correct	297 ms	80524 KB	Output is correct
34	Correct	199 ms	80524 KB	Output is correct
35	Correct	229 ms	85076 KB	Output is correct
36	Correct	156 ms	85076 KB	Output is correct
37	Correct	275 ms	89600 KB	Output is correct
38	Correct	187 ms	89600 KB	Output is correct
39	Correct	217 ms	97792 KB	Output is correct
40	Correct	273 ms	97792 KB	Output is correct
41	Correct	7 ms	97792 KB	Output is correct
42	Correct	7 ms	97792 KB	Output is correct
43	Correct	7 ms	97792 KB	Output is correct
44	Correct	9 ms	97792 KB	Output is correct
45	Correct	7 ms	97792 KB	Output is correct
46	Correct	10 ms	97792 KB	Output is correct
47	Correct	7 ms	97792 KB	Output is correct
48	Correct	7 ms	97792 KB	Output is correct
49	Correct	7 ms	97792 KB	Output is correct
50	Correct	7 ms	97792 KB	Output is correct
51	Correct	213 ms	97792 KB	Output is correct
52	Correct	155 ms	105820 KB	Output is correct
53	Correct	273 ms	105820 KB	Output is correct
54	Correct	152 ms	105820 KB	Output is correct
55	Correct	221 ms	107496 KB	Output is correct
56	Correct	152 ms	116856 KB	Output is correct
57	Correct	216 ms	116856 KB	Output is correct
58	Correct	155 ms	116856 KB	Output is correct
59	Correct	222 ms	118824 KB	Output is correct
60	Correct	155 ms	127888 KB	Output is correct
61	Correct	235 ms	127888 KB	Output is correct
62	Correct	160 ms	127888 KB	Output is correct
63	Correct	206 ms	129500 KB	Output is correct
64	Correct	138 ms	138808 KB	Output is correct
65	Correct	260 ms	138808 KB	Output is correct
66	Correct	151 ms	138808 KB	Output is correct
67	Correct	220 ms	140484 KB	Output is correct
68	Correct	143 ms	149804 KB	Output is correct
69	Correct	247 ms	149804 KB	Output is correct
70	Correct	169 ms	149804 KB	Output is correct

답안 #87221

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 30.0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
30.0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
40.0 / 40.0