oj.uz

Submission #105382

# Submission time Handle Problem Language Result Execution time Memory
105382 2019-04-11T16:32:07 Z reality Designated Cities (JOI19_designated_cities) C++17
100 / 100
 1603 ms 159376 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
map < int , int > cost[N];
set < int > g[N];
ll Answer[N];
ll sum = 0;
ll dfs(int node,int prev) {
    ll cnt = 0;
    for (auto it : g[node])
        if (it != prev)
            cnt += dfs(it,node) + cost[it][node];
    return cnt;
}
void DFS(int node,int prev) {
    smax(Answer[1],sum);
    for (auto it : g[node])
        if (it != prev) {
            sum -= cost[it][node] - cost[node][it];
            DFS(it,node);
            sum += cost[it][node] - cost[node][it];
        }
}
int main(void) {
    int n;
    cin.tie(0);
    ios_base :: sync_with_stdio(0);
    cin>>n;
    ll Sum = 0;
    for (int i = 1;i < n;++i) {
        int u,v,a,b;
        cin>>u>>v>>a>>b;
        cost[u][v] = a;
        cost[v][u] = b;
        g[u].insert(v);
        g[v].insert(u);
        Sum += a + b;
    }
    sum = dfs(1,0);
    DFS(1,0);
    Answer[1] = Sum - Answer[1];
    priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
    auto par = [&](int node) {
        return *g[node].begin();
    };
    for (int i = 1;i <= n;++i)
        if (g[i].size() == 1)
            Q.push(mp(cost[par(i)][i],i));
    int sz = Q.size() - 1;
    while (sz > 1) {
        ll cst = Q.top().fi;
        int node = Q.top().se;
        Q.pop();
        const int Par = par(node);
        g[Par].erase(node);
        if (g[Par].size() == 1)
            Q.push(mp(cst + cost[par(Par)][Par],Par));
        else {
            Answer[sz] = Answer[sz + 1] + cst;
            --sz;
        }
    }
    int q;
    cin>>q;
    while (q --) {
        int cnt;
        cin>>cnt;
        cout << Answer[cnt] << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94260 KB Output is correct
2 Correct 99 ms 94196 KB Output is correct
3 Correct 96 ms 94264 KB Output is correct
4 Correct 93 ms 94324 KB Output is correct
5 Correct 100 ms 94416 KB Output is correct
6 Correct 96 ms 94316 KB Output is correct
7 Correct 89 ms 94200 KB Output is correct
8 Correct 82 ms 94200 KB Output is correct
9 Correct 84 ms 94328 KB Output is correct
10 Correct 90 ms 94200 KB Output is correct
11 Correct 94 ms 94328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 94200 KB Output is correct
2 Correct 1151 ms 137036 KB Output is correct
3 Correct 925 ms 152024 KB Output is correct
4 Correct 1018 ms 136592 KB Output is correct
5 Correct 1216 ms 136500 KB Output is correct
6 Correct 1055 ms 138732 KB Output is correct
7 Correct 1404 ms 137204 KB Output is correct
8 Correct 957 ms 152788 KB Output is correct
9 Correct 1530 ms 138996 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 94392 KB Output is correct
2 Correct 1020 ms 136028 KB Output is correct
3 Correct 891 ms 159044 KB Output is correct
4 Correct 1064 ms 139144 KB Output is correct
5 Correct 1228 ms 140576 KB Output is correct
6 Correct 1119 ms 143328 KB Output is correct
7 Correct 1463 ms 142572 KB Output is correct
8 Correct 1014 ms 150904 KB Output is correct
9 Correct 1603 ms 142824 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94260 KB Output is correct
2 Correct 99 ms 94196 KB Output is correct
3 Correct 96 ms 94264 KB Output is correct
4 Correct 93 ms 94324 KB Output is correct
5 Correct 100 ms 94416 KB Output is correct
6 Correct 96 ms 94316 KB Output is correct
7 Correct 89 ms 94200 KB Output is correct
8 Correct 82 ms 94200 KB Output is correct
9 Correct 84 ms 94328 KB Output is correct
10 Correct 90 ms 94200 KB Output is correct
11 Correct 94 ms 94328 KB Output is correct
12 Correct 93 ms 94272 KB Output is correct
13 Correct 97 ms 94840 KB Output is correct
14 Correct 100 ms 94924 KB Output is correct
15 Correct 94 ms 94744 KB Output is correct
16 Correct 99 ms 94700 KB Output is correct
17 Correct 98 ms 94840 KB Output is correct
18 Correct 95 ms 94816 KB Output is correct
19 Correct 97 ms 94840 KB Output is correct
20 Correct 115 ms 94712 KB Output is correct
21 Correct 102 ms 94756 KB Output is correct
22 Correct 110 ms 94784 KB Output is correct
23 Correct 112 ms 94712 KB Output is correct
24 Correct 96 ms 94840 KB Output is correct
25 Correct 102 ms 94948 KB Output is correct
26 Correct 95 ms 94840 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 94200 KB Output is correct
2 Correct 1151 ms 137036 KB Output is correct
3 Correct 925 ms 152024 KB Output is correct
4 Correct 1018 ms 136592 KB Output is correct
5 Correct 1216 ms 136500 KB Output is correct
6 Correct 1055 ms 138732 KB Output is correct
7 Correct 1404 ms 137204 KB Output is correct
8 Correct 957 ms 152788 KB Output is correct
9 Correct 1530 ms 138996 KB Output is correct
10 Correct 84 ms 94392 KB Output is correct
11 Correct 1020 ms 136028 KB Output is correct
12 Correct 891 ms 159044 KB Output is correct
13 Correct 1064 ms 139144 KB Output is correct
14 Correct 1228 ms 140576 KB Output is correct
15 Correct 1119 ms 143328 KB Output is correct
16 Correct 1463 ms 142572 KB Output is correct
17 Correct 1014 ms 150904 KB Output is correct
18 Correct 1603 ms 142824 KB Output is correct
19 Correct 89 ms 94324 KB Output is correct
20 Correct 1077 ms 140564 KB Output is correct
21 Correct 847 ms 159376 KB Output is correct
22 Correct 976 ms 139380 KB Output is correct
23 Correct 1028 ms 140528 KB Output is correct
24 Correct 1069 ms 139360 KB Output is correct
25 Correct 1042 ms 140656 KB Output is correct
26 Correct 1087 ms 139332 KB Output is correct
27 Correct 1152 ms 140724 KB Output is correct
28 Correct 994 ms 142704 KB Output is correct
29 Correct 1104 ms 140848 KB Output is correct
30 Correct 1184 ms 139900 KB Output is correct
31 Correct 1472 ms 142616 KB Output is correct
32 Correct 950 ms 151792 KB Output is correct
33 Correct 1376 ms 143232 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94260 KB Output is correct
2 Correct 99 ms 94196 KB Output is correct
3 Correct 96 ms 94264 KB Output is correct
4 Correct 93 ms 94324 KB Output is correct
5 Correct 100 ms 94416 KB Output is correct
6 Correct 96 ms 94316 KB Output is correct
7 Correct 89 ms 94200 KB Output is correct
8 Correct 82 ms 94200 KB Output is correct
9 Correct 84 ms 94328 KB Output is correct
10 Correct 90 ms 94200 KB Output is correct
11 Correct 94 ms 94328 KB Output is correct
12 Correct 78 ms 94200 KB Output is correct
13 Correct 1151 ms 137036 KB Output is correct
14 Correct 925 ms 152024 KB Output is correct
15 Correct 1018 ms 136592 KB Output is correct
16 Correct 1216 ms 136500 KB Output is correct
17 Correct 1055 ms 138732 KB Output is correct
18 Correct 1404 ms 137204 KB Output is correct
19 Correct 957 ms 152788 KB Output is correct
20 Correct 1530 ms 138996 KB Output is correct
21 Correct 84 ms 94392 KB Output is correct
22 Correct 1020 ms 136028 KB Output is correct
23 Correct 891 ms 159044 KB Output is correct
24 Correct 1064 ms 139144 KB Output is correct
25 Correct 1228 ms 140576 KB Output is correct
26 Correct 1119 ms 143328 KB Output is correct
27 Correct 1463 ms 142572 KB Output is correct
28 Correct 1014 ms 150904 KB Output is correct
29 Correct 1603 ms 142824 KB Output is correct
30 Correct 93 ms 94272 KB Output is correct
31 Correct 97 ms 94840 KB Output is correct
32 Correct 100 ms 94924 KB Output is correct
33 Correct 94 ms 94744 KB Output is correct
34 Correct 99 ms 94700 KB Output is correct
35 Correct 98 ms 94840 KB Output is correct
36 Correct 95 ms 94816 KB Output is correct
37 Correct 97 ms 94840 KB Output is correct
38 Correct 115 ms 94712 KB Output is correct
39 Correct 102 ms 94756 KB Output is correct
40 Correct 110 ms 94784 KB Output is correct
41 Correct 112 ms 94712 KB Output is correct
42 Correct 96 ms 94840 KB Output is correct
43 Correct 102 ms 94948 KB Output is correct
44 Correct 95 ms 94840 KB Output is correct
45 Correct 89 ms 94324 KB Output is correct
46 Correct 1077 ms 140564 KB Output is correct
47 Correct 847 ms 159376 KB Output is correct
48 Correct 976 ms 139380 KB Output is correct
49 Correct 1028 ms 140528 KB Output is correct
50 Correct 1069 ms 139360 KB Output is correct
51 Correct 1042 ms 140656 KB Output is correct
52 Correct 1087 ms 139332 KB Output is correct
53 Correct 1152 ms 140724 KB Output is correct
54 Correct 994 ms 142704 KB Output is correct
55 Correct 1104 ms 140848 KB Output is correct
56 Correct 1184 ms 139900 KB Output is correct
57 Correct 1472 ms 142616 KB Output is correct
58 Correct 950 ms 151792 KB Output is correct
59 Correct 1376 ms 143232 KB Output is correct
60 Correct 108 ms 94312 KB Output is correct
61 Correct 1179 ms 143052 KB Output is correct
62 Correct 987 ms 157880 KB Output is correct
63 Correct 1012 ms 141860 KB Output is correct
64 Correct 1161 ms 143168 KB Output is correct
65 Correct 1151 ms 141744 KB Output is correct
66 Correct 1168 ms 143080 KB Output is correct
67 Correct 1133 ms 141604 KB Output is correct
68 Correct 1316 ms 143348 KB Output is correct
69 Correct 1149 ms 145280 KB Output is correct
70 Correct 1077 ms 142956 KB Output is correct
71 Correct 1173 ms 142816 KB Output is correct
72 Correct 1462 ms 144996 KB Output is correct
73 Correct 956 ms 152204 KB Output is correct
74 Correct 1485 ms 147388 KB Output is correct