oj.uz

Submission #1035260

# Submission time Handle Problem Language Result Execution time Memory
1035260 2024-07-26T08:06:49 Z shenfe1 Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 2011 ms 405652 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
 
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define ppb pop_back
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define lb lower_bound
#define mem(a,i) memset(a,i,sizeof(a))

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MAX=2e5+10;
 
int n,m;
 
struct DSU{
    int f[MAX];
 
    void init(int n){
        for(int i=1;i<=n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }
 
    void unite(int a,int b){
        a=get(a);
        b=get(b);
        f[a]=b;
    }
}D;


struct segtree{
    ll t[30*MAX];
    int L[30*MAX],R[30*MAX];
    int zs;

    segtree(){
        mem(t,0);
        mem(L,0);
        mem(R,0);
        zs=1;
    }
    
    void update(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            t[v]+=x;
            return;
        }
        int tm=(tl+tr)/2;
        if(!L[v]){
            L[v]=++zs;
        }
        if(!R[v]){
            R[v]=++zs;
        }
        update(L[v],tl,tm,l,r,x);
        update(R[v],tm+1,tr,l,r,x);
    }

    ll get(int v,int tl,int tr,int pos){
        if(tl==tr)return t[v];
        int tm=(tl+tr)/2;
        if(!L[v]){
            L[v]=++zs;
        }
        if(!R[v]){
            R[v]=++zs;
        }
        t[L[v]]+=t[v];
        t[R[v]]+=t[v];
        t[v]=0;
        if(pos<=tm){
            return get(L[v],tl,tm,pos);
        }
        else{
            return get(R[v],tm+1,tr,pos);
        }
    }
}T[2];

vector<pair<int,pii>> e;
set<pii> g[MAX];
int d[510];

void dfs(int v,int p=-1){
    for(auto to:g[v]){
        if(to.F==p)continue;
        d[to.F]=max(d[v],to.S);
        dfs(to.F,v);
    }
}

void dfs1(int v,int p=-1){
    for(auto to:g[v]){
        if(to.F==p)continue;
        d[to.F]=min(d[v],to.S);
        dfs1(to.F,v);
    }
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e.pb({c,{a,b}});
    }
    sort(all(e));
    D.init(n);
    for(int i=m-1;i>=0;i--){
        if(D.get(e[i].S.F)!=D.get(e[i].S.S)){
            D.unite(e[i].S.F,e[i].S.S);
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
            // if(e[i].F<=10)cout<<i<<" "<<10-e[i].F<<"\n";
            T[0].update(1,0,1e9,e[i].F,1e9,-e[i].F);
            T[1].update(1,0,1e9,e[i].F,1e9,1);
        }
        else{
            mem(d,0);
            dfs(e[i].S.F);
            int edge=d[e[i].S.S];
            g[e[edge].S.F].erase({e[edge].S.S,edge});
            g[e[edge].S.S].erase({e[edge].S.F,edge});
            {
                int pos=(e[i].F+e[edge].F)/2;
                // if(e[i].F<=10&&10<=pos)cout<<e[i].F<<" "<<e[edge].F<<" "<<pos<<" "<<10-e[i].F<<"\n";
                T[0].update(1,0,1e9,e[i].F,pos,-e[i].F);
                T[1].update(1,0,1e9,e[i].F,pos,1);
            }
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
        }
    }
    D.init(n);
    for(int i=0;i<m;i++){
        if(D.get(e[i].S.F)!=D.get(e[i].S.S)){
            D.unite(e[i].S.F,e[i].S.S);
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
            T[0].update(1,0,1e9,0,e[i].F,e[i].F);
            T[1].update(1,0,1e9,0,e[i].F,-1);
        }
        else{
            for(int i=1;i<=n;i++)d[i]=1e9;
            dfs1(e[i].S.F);
            int edge=d[e[i].S.S];
            g[e[edge].S.F].erase({e[edge].S.S,edge});
            g[e[edge].S.S].erase({e[edge].S.F,edge});
            {
                int pos=(e[edge].F+e[i].F)/2+1;
                T[0].update(1,0,1e9,pos,e[i].F,e[i].F);
                T[1].update(1,0,1e9,pos,e[i].F,-1);
            }    
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
        }
    }
    int q;
    cin>>q;
    while(q--){
        int d;
        cin>>d;
        cout<<T[0].get(1,0,1e9,d)+T[1].get(1,0,1e9,d)*d<<"\n";
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    int init=clock();
    while(t--)solve();
    #ifdef LOCAL
        cout.precision(10);
        cout<<fixed<<1.0*(clock()-init)/CLOCKS_PER_SEC<<"\n";
    #endif
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:186:9: warning: unused variable 'init' [-Wunused-variable]
  186 |     int init=clock();
      |         ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 197612 KB Output is correct
2 Correct 77 ms 197688 KB Output is correct
3 Correct 77 ms 197460 KB Output is correct
4 Correct 74 ms 197716 KB Output is correct
5 Correct 76 ms 197664 KB Output is correct
6 Correct 75 ms 197488 KB Output is correct
7 Correct 75 ms 197712 KB Output is correct
8 Correct 78 ms 197716 KB Output is correct
9 Correct 74 ms 197700 KB Output is correct
10 Correct 75 ms 197536 KB Output is correct
11 Correct 78 ms 197716 KB Output is correct
12 Correct 77 ms 197512 KB Output is correct
13 Correct 75 ms 197588 KB Output is correct
14 Correct 77 ms 197596 KB Output is correct
15 Correct 77 ms 197496 KB Output is correct
16 Correct 76 ms 197712 KB Output is correct
17 Correct 76 ms 197632 KB Output is correct
18 Correct 76 ms 197544 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 197612 KB Output is correct
2 Correct 77 ms 197688 KB Output is correct
3 Correct 77 ms 197460 KB Output is correct
4 Correct 74 ms 197716 KB Output is correct
5 Correct 76 ms 197664 KB Output is correct
6 Correct 75 ms 197488 KB Output is correct
7 Correct 75 ms 197712 KB Output is correct
8 Correct 78 ms 197716 KB Output is correct
9 Correct 74 ms 197700 KB Output is correct
10 Correct 75 ms 197536 KB Output is correct
11 Correct 78 ms 197716 KB Output is correct
12 Correct 77 ms 197512 KB Output is correct
13 Correct 75 ms 197588 KB Output is correct
14 Correct 77 ms 197596 KB Output is correct
15 Correct 77 ms 197496 KB Output is correct
16 Correct 76 ms 197712 KB Output is correct
17 Correct 76 ms 197632 KB Output is correct
18 Correct 76 ms 197544 KB Output is correct
19 Correct 76 ms 197716 KB Output is correct
20 Correct 2011 ms 199368 KB Output is correct
21 Correct 1362 ms 200652 KB Output is correct
22 Correct 1591 ms 200504 KB Output is correct
23 Correct 1689 ms 200652 KB Output is correct
24 Correct 1787 ms 200616 KB Output is correct
25 Correct 1841 ms 200648 KB Output is correct
26 Correct 1783 ms 200648 KB Output is correct
27 Correct 1774 ms 200648 KB Output is correct
28 Correct 1730 ms 200652 KB Output is correct
29 Correct 973 ms 200652 KB Output is correct
30 Correct 1994 ms 200520 KB Output is correct
31 Correct 1857 ms 200540 KB Output is correct
32 Correct 1878 ms 200740 KB Output is correct
33 Correct 1947 ms 200652 KB Output is correct
34 Correct 745 ms 200652 KB Output is correct
35 Correct 1883 ms 200648 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 197460 KB Output is correct
2 Correct 81 ms 197464 KB Output is correct
3 Correct 76 ms 197600 KB Output is correct
4 Runtime error 1819 ms 405444 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 197612 KB Output is correct
2 Correct 77 ms 197688 KB Output is correct
3 Correct 77 ms 197460 KB Output is correct
4 Correct 74 ms 197716 KB Output is correct
5 Correct 76 ms 197664 KB Output is correct
6 Correct 75 ms 197488 KB Output is correct
7 Correct 75 ms 197712 KB Output is correct
8 Correct 78 ms 197716 KB Output is correct
9 Correct 74 ms 197700 KB Output is correct
10 Correct 75 ms 197536 KB Output is correct
11 Correct 78 ms 197716 KB Output is correct
12 Correct 77 ms 197512 KB Output is correct
13 Correct 75 ms 197588 KB Output is correct
14 Correct 77 ms 197596 KB Output is correct
15 Correct 77 ms 197496 KB Output is correct
16 Correct 76 ms 197712 KB Output is correct
17 Correct 76 ms 197632 KB Output is correct
18 Correct 76 ms 197544 KB Output is correct
19 Correct 76 ms 197712 KB Output is correct
20 Runtime error 356 ms 405652 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 197612 KB Output is correct
2 Correct 77 ms 197688 KB Output is correct
3 Correct 77 ms 197460 KB Output is correct
4 Correct 74 ms 197716 KB Output is correct
5 Correct 76 ms 197664 KB Output is correct
6 Correct 75 ms 197488 KB Output is correct
7 Correct 75 ms 197712 KB Output is correct
8 Correct 78 ms 197716 KB Output is correct
9 Correct 74 ms 197700 KB Output is correct
10 Correct 75 ms 197536 KB Output is correct
11 Correct 78 ms 197716 KB Output is correct
12 Correct 77 ms 197512 KB Output is correct
13 Correct 75 ms 197588 KB Output is correct
14 Correct 77 ms 197596 KB Output is correct
15 Correct 77 ms 197496 KB Output is correct
16 Correct 76 ms 197712 KB Output is correct
17 Correct 76 ms 197632 KB Output is correct
18 Correct 76 ms 197544 KB Output is correct
19 Correct 76 ms 197716 KB Output is correct
20 Correct 2011 ms 199368 KB Output is correct
21 Correct 1362 ms 200652 KB Output is correct
22 Correct 1591 ms 200504 KB Output is correct
23 Correct 1689 ms 200652 KB Output is correct
24 Correct 1787 ms 200616 KB Output is correct
25 Correct 1841 ms 200648 KB Output is correct
26 Correct 1783 ms 200648 KB Output is correct
27 Correct 1774 ms 200648 KB Output is correct
28 Correct 1730 ms 200652 KB Output is correct
29 Correct 973 ms 200652 KB Output is correct
30 Correct 1994 ms 200520 KB Output is correct
31 Correct 1857 ms 200540 KB Output is correct
32 Correct 1878 ms 200740 KB Output is correct
33 Correct 1947 ms 200652 KB Output is correct
34 Correct 745 ms 200652 KB Output is correct
35 Correct 1883 ms 200648 KB Output is correct
36 Correct 1942 ms 200900 KB Output is correct
37 Correct 1388 ms 201152 KB Output is correct
38 Correct 1548 ms 201148 KB Output is correct
39 Correct 1587 ms 201152 KB Output is correct
40 Correct 1736 ms 200936 KB Output is correct
41 Correct 1783 ms 200912 KB Output is correct
42 Correct 1844 ms 200936 KB Output is correct
43 Correct 1951 ms 201160 KB Output is correct
44 Correct 1649 ms 200932 KB Output is correct
45 Correct 902 ms 200940 KB Output is correct
46 Correct 1990 ms 200912 KB Output is correct
47 Correct 1872 ms 200904 KB Output is correct
48 Correct 1935 ms 200904 KB Output is correct
49 Correct 1909 ms 201100 KB Output is correct
50 Correct 750 ms 201156 KB Output is correct
51 Correct 1882 ms 200900 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 197612 KB Output is correct
2 Correct 77 ms 197688 KB Output is correct
3 Correct 77 ms 197460 KB Output is correct
4 Correct 74 ms 197716 KB Output is correct
5 Correct 76 ms 197664 KB Output is correct
6 Correct 75 ms 197488 KB Output is correct
7 Correct 75 ms 197712 KB Output is correct
8 Correct 78 ms 197716 KB Output is correct
9 Correct 74 ms 197700 KB Output is correct
10 Correct 75 ms 197536 KB Output is correct
11 Correct 78 ms 197716 KB Output is correct
12 Correct 77 ms 197512 KB Output is correct
13 Correct 75 ms 197588 KB Output is correct
14 Correct 77 ms 197596 KB Output is correct
15 Correct 77 ms 197496 KB Output is correct
16 Correct 76 ms 197712 KB Output is correct
17 Correct 76 ms 197632 KB Output is correct
18 Correct 76 ms 197544 KB Output is correct
19 Correct 76 ms 197716 KB Output is correct
20 Correct 2011 ms 199368 KB Output is correct
21 Correct 1362 ms 200652 KB Output is correct
22 Correct 1591 ms 200504 KB Output is correct
23 Correct 1689 ms 200652 KB Output is correct
24 Correct 1787 ms 200616 KB Output is correct
25 Correct 1841 ms 200648 KB Output is correct
26 Correct 1783 ms 200648 KB Output is correct
27 Correct 1774 ms 200648 KB Output is correct
28 Correct 1730 ms 200652 KB Output is correct
29 Correct 973 ms 200652 KB Output is correct
30 Correct 1994 ms 200520 KB Output is correct
31 Correct 1857 ms 200540 KB Output is correct
32 Correct 1878 ms 200740 KB Output is correct
33 Correct 1947 ms 200652 KB Output is correct
34 Correct 745 ms 200652 KB Output is correct
35 Correct 1883 ms 200648 KB Output is correct
36 Correct 78 ms 197460 KB Output is correct
37 Correct 81 ms 197464 KB Output is correct
38 Correct 76 ms 197600 KB Output is correct
39 Runtime error 1819 ms 405444 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -