oj.uz

Submission #777081

# Submission time Handle Problem Language Result Execution time Memory
777081 2023-07-08T15:50:33 Z bachhoangxuan Designated Cities (JOI19_designated_cities) C++17
100 / 100
 321 ms 69688 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=200005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;
struct ed{
    int u,c,d;
};
vector<ed> edge[maxn];
pii mx[maxn];
int dd[maxn],ans[maxn];
void solve(){
    int n;cin >> n;
    for(int i=1;i<n;i++){
        int u,v,c,d;cin >> u >> v >> c >> d;
        edge[u].push_back({v,c,d});
        edge[v].push_back({u,d,c});
    }
    int sum=0,Max=0,su=-1,sv=-1;
    function<void(int,int)> dfs = [&](int u,int p){
        ans[1]=max(ans[1],dd[u]);
        pii cur={0,u};
        for(auto &[v,c,d]:edge[u]){
            if(v==p) continue;
            dd[v]=dd[u]+c-d,sum+=c;dfs(v,u);
            if(cur.fi+c+mx[v].fi+dd[u]>Max){
                Max=cur.fi+c+mx[v].fi+dd[u];
                su=cur.se;sv=mx[v].se;
            }
            cur=max(cur,{mx[v].fi+c,mx[v].se});
        }
        mx[u]=cur;
    };
    dfs(1,0);
    ans[1]=sum-ans[1];sum=0;
    vector<vector<int>> w(n+1);
    function<void(int,int)> dfs2 = [&](int u,int p){
        w[u].push_back(0);
        for(auto &[v,c,d]:edge[u]){
            if(v==p) continue;
            dfs2(v,u);w[v].back()+=c;sum+=c;
            if((int)w[v].size()>(int)w[u].size()) swap(w[u],w[v]);
            if(w[u].back()>w[v].back()) swap(w[u].back(),w[v].back());
            for(int x:w[v]) w[u].push_back(x);
        }
    };
    dfs2(su,0);
    sort(w[su].begin(),w[su].end(),greater<int>());
    for(int i=2;i<=n;i++) ans[i]=(i==2?sum:ans[i-1])-w[su][i-2];
    int q;cin >> q;
    for(int i=1;i<=q;i++){
        int x;cin >> x;
        cout << ans[x] << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5052 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5036 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 219 ms 49820 KB Output is correct
3 Correct 279 ms 67792 KB Output is correct
4 Correct 202 ms 48760 KB Output is correct
5 Correct 208 ms 45068 KB Output is correct
6 Correct 220 ms 48444 KB Output is correct
7 Correct 177 ms 42716 KB Output is correct
8 Correct 250 ms 66492 KB Output is correct
9 Correct 130 ms 41176 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5040 KB Output is correct
2 Correct 228 ms 49920 KB Output is correct
3 Correct 249 ms 67924 KB Output is correct
4 Correct 207 ms 48780 KB Output is correct
5 Correct 193 ms 44988 KB Output is correct
6 Correct 225 ms 49108 KB Output is correct
7 Correct 145 ms 41196 KB Output is correct
8 Correct 234 ms 58920 KB Output is correct
9 Correct 143 ms 40856 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5052 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5036 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 4 ms 5688 KB Output is correct
15 Correct 4 ms 5460 KB Output is correct
16 Correct 4 ms 5460 KB Output is correct
17 Correct 4 ms 5460 KB Output is correct
18 Correct 4 ms 5428 KB Output is correct
19 Correct 4 ms 5460 KB Output is correct
20 Correct 5 ms 5432 KB Output is correct
21 Correct 4 ms 5460 KB Output is correct
22 Correct 4 ms 5432 KB Output is correct
23 Correct 4 ms 5460 KB Output is correct
24 Correct 3 ms 5332 KB Output is correct
25 Correct 4 ms 5588 KB Output is correct
26 Correct 4 ms 5332 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 219 ms 49820 KB Output is correct
3 Correct 279 ms 67792 KB Output is correct
4 Correct 202 ms 48760 KB Output is correct
5 Correct 208 ms 45068 KB Output is correct
6 Correct 220 ms 48444 KB Output is correct
7 Correct 177 ms 42716 KB Output is correct
8 Correct 250 ms 66492 KB Output is correct
9 Correct 130 ms 41176 KB Output is correct
10 Correct 2 ms 5040 KB Output is correct
11 Correct 228 ms 49920 KB Output is correct
12 Correct 249 ms 67924 KB Output is correct
13 Correct 207 ms 48780 KB Output is correct
14 Correct 193 ms 44988 KB Output is correct
15 Correct 225 ms 49108 KB Output is correct
16 Correct 145 ms 41196 KB Output is correct
17 Correct 234 ms 58920 KB Output is correct
18 Correct 143 ms 40856 KB Output is correct
19 Correct 3 ms 5032 KB Output is correct
20 Correct 209 ms 50080 KB Output is correct
21 Correct 245 ms 67812 KB Output is correct
22 Correct 194 ms 48848 KB Output is correct
23 Correct 214 ms 49724 KB Output is correct
24 Correct 214 ms 49264 KB Output is correct
25 Correct 219 ms 50488 KB Output is correct
26 Correct 203 ms 48828 KB Output is correct
27 Correct 191 ms 45008 KB Output is correct
28 Correct 255 ms 48624 KB Output is correct
29 Correct 231 ms 49724 KB Output is correct
30 Correct 197 ms 47892 KB Output is correct
31 Correct 164 ms 42156 KB Output is correct
32 Correct 251 ms 59628 KB Output is correct
33 Correct 162 ms 41196 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5052 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5036 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 219 ms 49820 KB Output is correct
14 Correct 279 ms 67792 KB Output is correct
15 Correct 202 ms 48760 KB Output is correct
16 Correct 208 ms 45068 KB Output is correct
17 Correct 220 ms 48444 KB Output is correct
18 Correct 177 ms 42716 KB Output is correct
19 Correct 250 ms 66492 KB Output is correct
20 Correct 130 ms 41176 KB Output is correct
21 Correct 2 ms 5040 KB Output is correct
22 Correct 228 ms 49920 KB Output is correct
23 Correct 249 ms 67924 KB Output is correct
24 Correct 207 ms 48780 KB Output is correct
25 Correct 193 ms 44988 KB Output is correct
26 Correct 225 ms 49108 KB Output is correct
27 Correct 145 ms 41196 KB Output is correct
28 Correct 234 ms 58920 KB Output is correct
29 Correct 143 ms 40856 KB Output is correct
30 Correct 2 ms 4948 KB Output is correct
31 Correct 4 ms 5460 KB Output is correct
32 Correct 4 ms 5688 KB Output is correct
33 Correct 4 ms 5460 KB Output is correct
34 Correct 4 ms 5460 KB Output is correct
35 Correct 4 ms 5460 KB Output is correct
36 Correct 4 ms 5428 KB Output is correct
37 Correct 4 ms 5460 KB Output is correct
38 Correct 5 ms 5432 KB Output is correct
39 Correct 4 ms 5460 KB Output is correct
40 Correct 4 ms 5432 KB Output is correct
41 Correct 4 ms 5460 KB Output is correct
42 Correct 3 ms 5332 KB Output is correct
43 Correct 4 ms 5588 KB Output is correct
44 Correct 4 ms 5332 KB Output is correct
45 Correct 3 ms 5032 KB Output is correct
46 Correct 209 ms 50080 KB Output is correct
47 Correct 245 ms 67812 KB Output is correct
48 Correct 194 ms 48848 KB Output is correct
49 Correct 214 ms 49724 KB Output is correct
50 Correct 214 ms 49264 KB Output is correct
51 Correct 219 ms 50488 KB Output is correct
52 Correct 203 ms 48828 KB Output is correct
53 Correct 191 ms 45008 KB Output is correct
54 Correct 255 ms 48624 KB Output is correct
55 Correct 231 ms 49724 KB Output is correct
56 Correct 197 ms 47892 KB Output is correct
57 Correct 164 ms 42156 KB Output is correct
58 Correct 251 ms 59628 KB Output is correct
59 Correct 162 ms 41196 KB Output is correct
60 Correct 2 ms 4948 KB Output is correct
61 Correct 282 ms 53208 KB Output is correct
62 Correct 321 ms 69688 KB Output is correct
63 Correct 266 ms 51804 KB Output is correct
64 Correct 258 ms 53180 KB Output is correct
65 Correct 259 ms 51564 KB Output is correct
66 Correct 246 ms 52964 KB Output is correct
67 Correct 273 ms 51712 KB Output is correct
68 Correct 224 ms 48096 KB Output is correct
69 Correct 290 ms 51292 KB Output is correct
70 Correct 234 ms 52064 KB Output is correct
71 Correct 226 ms 50428 KB Output is correct
72 Correct 247 ms 45880 KB Output is correct
73 Correct 268 ms 61728 KB Output is correct
74 Correct 170 ms 45400 KB Output is correct