oj.uz

Submission #380480

# Submission time Handle Problem Language Result Execution time Memory
380480 2021-03-22T03:21:15 Z i_am_noob Designated Cities (JOI19_designated_cities) C++17
100 / 100
 669 ms 70892 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;

#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

inline char readchar(){
    const int maxn=1000000;
    static char buf[maxn],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
    else return *p++;
}
inline int readint(){
    int c=readchar(),x=0,neg=0;
    while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
    if(c=='-') neg=1,c=readchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
    return neg?-x:x;
}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=200005;
//i_am_noob
int n,par[maxn],up[maxn],down[maxn],arr[maxn],dp[maxn],dpid[maxn],sumd,sumu,minid,k1,k2,lpos[maxn],rpos[maxn],rev[maxn];
int val[maxn*4],maxid[maxn*4],tag[maxn*4];
int ans[maxn];
vector<pii> adj[maxn];
bool vis[maxn];

void dfs1(int u, int p){
    par[u]=p;
    for(auto& [v,w]: adj[u]){
        if(v==p) up[u]=w,sumu+=w;
        else{
            dfs1(v,u);
            sumd+=w;
            down[v]=w;
        }
    }
}

void dfs2(int u, int p, int curd, int curu){
    arr[u]=0;
    dp[u]=0;
    int cnt=0;
    for(auto& [v,w]: adj[u]) if(v!=p){
        dfs2(v,u,curd+w,curu+up[v]);
        arr[u]+=arr[v]+w;
        cnt++;
        if(dp[v]+w>dp[u]) dp[u]=dp[v]+w,dpid[u]=dpid[v];
    }
    if(!cnt) dpid[u]=u;
    ans[1]=min(ans[1],sumd-curd+curu);
    if(cnt>=2){
        vector<pii> vec;
        for(auto& [v,w]: adj[u]) if(v!=p) vec.pb({dp[v]+w,dpid[v]});
        sort(all(vec));
        reverse(all(vec));
        int tmp=sumd-curd-(vec[0].first+vec[1].first)+curu;
        if(tmp<ans[2]) ans[2]=tmp,minid=u,k1=vec[0].second,k2=vec[1].second;
    }
}

void dfs3(int u, int p, int cur){
    int cnt=0;
    for(auto& [v,w]: adj[u]) if(v!=p) {
        cnt++;
        dfs3(v,u,cur+w);
    }
    if(!cnt) arr[lpos[u]]=cur;
    else arr[lpos[u]]=-inf;
}

void dfs4(int u, int p){
    static int t=0;
    lpos[u]=t++;
    rev[t-1]=u;
    for(auto& [v,w]: adj[u]) if(v!=p) dfs4(v,u);
    rpos[u]=t-1;
    bug(u,lpos[u],rpos[u]);
}

void pull(int k){
    val[k]=max(val[k<<1],val[k<<1|1]);
    if(val[k]==val[k<<1]) maxid[k]=maxid[k<<1];
    else maxid[k]=maxid[k<<1|1];
}

void push(int k, int l, int r){
    if(l!=r){
        val[k<<1]+=tag[k],val[k<<1|1]+=tag[k];
        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
    }
    tag[k]=0;
}

void build(int k, int l, int r){
    if(l==r){
        val[k]=arr[l];
        maxid[k]=l;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    pull(k);
}

void modify(int k, int l, int r, int ql, int qr, int x){
    if(ql>r||qr<l) return;
    if(ql<=l&&qr>=r){
        val[k]+=x,tag[k]+=x;
        return;
    }
    int mid=l+r>>1;
    push(k,l,r);
    modify(k<<1,l,mid,ql,qr,x),modify(k<<1|1,mid+1,r,ql,qr,x);
    pull(k);
}

void modify(int u){
    for(int i=u; !vis[i]; i=par[i]){
        bug(i,down[i]);
        vis[i]=1;
        modify(1,0,n-1,lpos[i],rpos[i],-down[i]);
    }
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cin >> n;
    rep(n-1){
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        u--,v--;
        adj[u].pb({v,w1}),adj[v].pb({u,w2});
    }
    if(n==2){
        int q;
        cin >> q;
        while(q--){
            int k;
            cin >> k;
            if(k==1) cout << min(adj[0][0].second,adj[1][0].second) << "\n";
            else cout << "0\n";
        }
        return 0;
    }
    int tmp;
    rep(n) if(sz(adj[i])>1) tmp=i;
    dfs1(tmp,-1);
    ans[1]=ans[2]=inf;
    dfs2(tmp,-1,0,0);
    bug(minid);
    dfs1(minid,-1);
    dfs4(minid,-1);
    dfs3(minid,-1,0);
    vis[minid]=1;
    build(1,0,n-1);
    bug(k1,k2);
    bug(val[1],rev[maxid[1]]);
    modify(k1),modify(k2);
    bug(val[1],rev[maxid[1]]);
    rep2(i,3,n+1){
        if(ans[i-1]==0){
            ans[i]=0;
            continue;
        }
        int u=rev[maxid[1]];
        ans[i]=ans[i-1]-val[1];
        bug(u,val[1]);
        modify(u);
    }
    int q;
    cin >> q;
    while(q--){
        int k;
        cin >> k;
        cout << ans[k] << "\n";
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'void dfs4(long long int, long long int)':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:105:5: note: in expansion of macro 'bug'
  105 |     bug(u,lpos[u],rpos[u]);
      |     ^~~
designated_cities.cpp: In function 'void build(long long int, long long int, long long int)':
designated_cities.cpp:128:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |     int mid=l+r>>1;
      |             ~^~
designated_cities.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, long long int)':
designated_cities.cpp:139:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |     int mid=l+r>>1;
      |             ~^~
designated_cities.cpp: In function 'void modify(long long int)':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:147:9: note: in expansion of macro 'bug'
  147 |         bug(i,down[i]);
      |         ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:183:5: note: in expansion of macro 'bug'
  183 |     bug(minid);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:189:5: note: in expansion of macro 'bug'
  189 |     bug(k1,k2);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:190:5: note: in expansion of macro 'bug'
  190 |     bug(val[1],rev[maxid[1]]);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:192:5: note: in expansion of macro 'bug'
  192 |     bug(val[1],rev[maxid[1]]);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:200:9: note: in expansion of macro 'bug'
  200 |         bug(u,val[1]);
      |         ^~~
designated_cities.cpp:178:9: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  178 |     int tmp;
      |         ^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 599 ms 45036 KB Output is correct
3 Correct 651 ms 62700 KB Output is correct
4 Correct 547 ms 45548 KB Output is correct
5 Correct 580 ms 45364 KB Output is correct
6 Correct 597 ms 48492 KB Output is correct
7 Correct 527 ms 44868 KB Output is correct
8 Correct 654 ms 66284 KB Output is correct
9 Correct 465 ms 44600 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 605 ms 45164 KB Output is correct
3 Correct 613 ms 61676 KB Output is correct
4 Correct 543 ms 45292 KB Output is correct
5 Correct 586 ms 45140 KB Output is correct
6 Correct 603 ms 48620 KB Output is correct
7 Correct 461 ms 44344 KB Output is correct
8 Correct 647 ms 62720 KB Output is correct
9 Correct 473 ms 44328 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 7 ms 5612 KB Output is correct
14 Correct 7 ms 5868 KB Output is correct
15 Correct 7 ms 5612 KB Output is correct
16 Correct 8 ms 5612 KB Output is correct
17 Correct 7 ms 5612 KB Output is correct
18 Correct 7 ms 5612 KB Output is correct
19 Correct 7 ms 5612 KB Output is correct
20 Correct 7 ms 5612 KB Output is correct
21 Correct 8 ms 5612 KB Output is correct
22 Correct 7 ms 5612 KB Output is correct
23 Correct 7 ms 5612 KB Output is correct
24 Correct 7 ms 5740 KB Output is correct
25 Correct 7 ms 5740 KB Output is correct
26 Correct 7 ms 5612 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 599 ms 45036 KB Output is correct
3 Correct 651 ms 62700 KB Output is correct
4 Correct 547 ms 45548 KB Output is correct
5 Correct 580 ms 45364 KB Output is correct
6 Correct 597 ms 48492 KB Output is correct
7 Correct 527 ms 44868 KB Output is correct
8 Correct 654 ms 66284 KB Output is correct
9 Correct 465 ms 44600 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 605 ms 45164 KB Output is correct
12 Correct 613 ms 61676 KB Output is correct
13 Correct 543 ms 45292 KB Output is correct
14 Correct 586 ms 45140 KB Output is correct
15 Correct 603 ms 48620 KB Output is correct
16 Correct 461 ms 44344 KB Output is correct
17 Correct 647 ms 62720 KB Output is correct
18 Correct 473 ms 44328 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 608 ms 45188 KB Output is correct
21 Correct 623 ms 67800 KB Output is correct
22 Correct 527 ms 48696 KB Output is correct
23 Correct 623 ms 50288 KB Output is correct
24 Correct 579 ms 49004 KB Output is correct
25 Correct 578 ms 50284 KB Output is correct
26 Correct 588 ms 49132 KB Output is correct
27 Correct 562 ms 50020 KB Output is correct
28 Correct 595 ms 53356 KB Output is correct
29 Correct 582 ms 50668 KB Output is correct
30 Correct 552 ms 48844 KB Output is correct
31 Correct 498 ms 49372 KB Output is correct
32 Correct 666 ms 66284 KB Output is correct
33 Correct 446 ms 49312 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 599 ms 45036 KB Output is correct
14 Correct 651 ms 62700 KB Output is correct
15 Correct 547 ms 45548 KB Output is correct
16 Correct 580 ms 45364 KB Output is correct
17 Correct 597 ms 48492 KB Output is correct
18 Correct 527 ms 44868 KB Output is correct
19 Correct 654 ms 66284 KB Output is correct
20 Correct 465 ms 44600 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct
22 Correct 605 ms 45164 KB Output is correct
23 Correct 613 ms 61676 KB Output is correct
24 Correct 543 ms 45292 KB Output is correct
25 Correct 586 ms 45140 KB Output is correct
26 Correct 603 ms 48620 KB Output is correct
27 Correct 461 ms 44344 KB Output is correct
28 Correct 647 ms 62720 KB Output is correct
29 Correct 473 ms 44328 KB Output is correct
30 Correct 4 ms 5100 KB Output is correct
31 Correct 7 ms 5612 KB Output is correct
32 Correct 7 ms 5868 KB Output is correct
33 Correct 7 ms 5612 KB Output is correct
34 Correct 8 ms 5612 KB Output is correct
35 Correct 7 ms 5612 KB Output is correct
36 Correct 7 ms 5612 KB Output is correct
37 Correct 7 ms 5612 KB Output is correct
38 Correct 7 ms 5612 KB Output is correct
39 Correct 8 ms 5612 KB Output is correct
40 Correct 7 ms 5612 KB Output is correct
41 Correct 7 ms 5612 KB Output is correct
42 Correct 7 ms 5740 KB Output is correct
43 Correct 7 ms 5740 KB Output is correct
44 Correct 7 ms 5612 KB Output is correct
45 Correct 4 ms 5100 KB Output is correct
46 Correct 608 ms 45188 KB Output is correct
47 Correct 623 ms 67800 KB Output is correct
48 Correct 527 ms 48696 KB Output is correct
49 Correct 623 ms 50288 KB Output is correct
50 Correct 579 ms 49004 KB Output is correct
51 Correct 578 ms 50284 KB Output is correct
52 Correct 588 ms 49132 KB Output is correct
53 Correct 562 ms 50020 KB Output is correct
54 Correct 595 ms 53356 KB Output is correct
55 Correct 582 ms 50668 KB Output is correct
56 Correct 552 ms 48844 KB Output is correct
57 Correct 498 ms 49372 KB Output is correct
58 Correct 666 ms 66284 KB Output is correct
59 Correct 446 ms 49312 KB Output is correct
60 Correct 4 ms 5100 KB Output is correct
61 Correct 644 ms 52560 KB Output is correct
62 Correct 653 ms 70636 KB Output is correct
63 Correct 586 ms 51436 KB Output is correct
64 Correct 625 ms 52972 KB Output is correct
65 Correct 631 ms 51564 KB Output is correct
66 Correct 626 ms 52824 KB Output is correct
67 Correct 608 ms 51564 KB Output is correct
68 Correct 604 ms 52764 KB Output is correct
69 Correct 629 ms 55276 KB Output is correct
70 Correct 634 ms 53484 KB Output is correct
71 Correct 576 ms 51720 KB Output is correct
72 Correct 554 ms 52816 KB Output is correct
73 Correct 669 ms 70892 KB Output is correct
74 Correct 494 ms 53516 KB Output is correct