oj.uz

Submission #1035261

# Submission time Handle Problem Language Result Execution time Memory
1035261 2024-07-26T08:07:57 Z shenfe1 Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 2153 ms 394916 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=1e5+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[60*MAX];
    int L[60*MAX],R[60*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 76 ms 192884 KB Output is correct
2 Correct 76 ms 192932 KB Output is correct
3 Correct 76 ms 192964 KB Output is correct
4 Correct 76 ms 192852 KB Output is correct
5 Correct 77 ms 192852 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 76 ms 192884 KB Output is correct
8 Correct 77 ms 192852 KB Output is correct
9 Correct 81 ms 192800 KB Output is correct
10 Correct 82 ms 192848 KB Output is correct
11 Correct 81 ms 192804 KB Output is correct
12 Correct 80 ms 192984 KB Output is correct
13 Correct 78 ms 192856 KB Output is correct
14 Correct 81 ms 192848 KB Output is correct
15 Correct 81 ms 192912 KB Output is correct
16 Correct 76 ms 192848 KB Output is correct
17 Correct 75 ms 192852 KB Output is correct
18 Correct 87 ms 192940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 192884 KB Output is correct
2 Correct 76 ms 192932 KB Output is correct
3 Correct 76 ms 192964 KB Output is correct
4 Correct 76 ms 192852 KB Output is correct
5 Correct 77 ms 192852 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 76 ms 192884 KB Output is correct
8 Correct 77 ms 192852 KB Output is correct
9 Correct 81 ms 192800 KB Output is correct
10 Correct 82 ms 192848 KB Output is correct
11 Correct 81 ms 192804 KB Output is correct
12 Correct 80 ms 192984 KB Output is correct
13 Correct 78 ms 192856 KB Output is correct
14 Correct 81 ms 192848 KB Output is correct
15 Correct 81 ms 192912 KB Output is correct
16 Correct 76 ms 192848 KB Output is correct
17 Correct 75 ms 192852 KB Output is correct
18 Correct 87 ms 192940 KB Output is correct
19 Correct 75 ms 192852 KB Output is correct
20 Correct 1847 ms 194516 KB Output is correct
21 Correct 1399 ms 194508 KB Output is correct
22 Correct 1642 ms 194508 KB Output is correct
23 Correct 1772 ms 194504 KB Output is correct
24 Correct 1759 ms 194548 KB Output is correct
25 Correct 1895 ms 194508 KB Output is correct
26 Correct 1896 ms 194504 KB Output is correct
27 Correct 1897 ms 194504 KB Output is correct
28 Correct 1800 ms 194508 KB Output is correct
29 Correct 955 ms 194496 KB Output is correct
30 Correct 1883 ms 194504 KB Output is correct
31 Correct 1959 ms 194476 KB Output is correct
32 Correct 1974 ms 194560 KB Output is correct
33 Correct 1816 ms 194508 KB Output is correct
34 Correct 779 ms 194456 KB Output is correct
35 Correct 1886 ms 194508 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 192924 KB Output is correct
2 Correct 80 ms 192996 KB Output is correct
3 Correct 78 ms 192852 KB Output is correct
4 Runtime error 1898 ms 394916 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 76 ms 192884 KB Output is correct
2 Correct 76 ms 192932 KB Output is correct
3 Correct 76 ms 192964 KB Output is correct
4 Correct 76 ms 192852 KB Output is correct
5 Correct 77 ms 192852 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 76 ms 192884 KB Output is correct
8 Correct 77 ms 192852 KB Output is correct
9 Correct 81 ms 192800 KB Output is correct
10 Correct 82 ms 192848 KB Output is correct
11 Correct 81 ms 192804 KB Output is correct
12 Correct 80 ms 192984 KB Output is correct
13 Correct 78 ms 192856 KB Output is correct
14 Correct 81 ms 192848 KB Output is correct
15 Correct 81 ms 192912 KB Output is correct
16 Correct 76 ms 192848 KB Output is correct
17 Correct 75 ms 192852 KB Output is correct
18 Correct 87 ms 192940 KB Output is correct
19 Correct 77 ms 192912 KB Output is correct
20 Runtime error 349 ms 394856 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 76 ms 192884 KB Output is correct
2 Correct 76 ms 192932 KB Output is correct
3 Correct 76 ms 192964 KB Output is correct
4 Correct 76 ms 192852 KB Output is correct
5 Correct 77 ms 192852 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 76 ms 192884 KB Output is correct
8 Correct 77 ms 192852 KB Output is correct
9 Correct 81 ms 192800 KB Output is correct
10 Correct 82 ms 192848 KB Output is correct
11 Correct 81 ms 192804 KB Output is correct
12 Correct 80 ms 192984 KB Output is correct
13 Correct 78 ms 192856 KB Output is correct
14 Correct 81 ms 192848 KB Output is correct
15 Correct 81 ms 192912 KB Output is correct
16 Correct 76 ms 192848 KB Output is correct
17 Correct 75 ms 192852 KB Output is correct
18 Correct 87 ms 192940 KB Output is correct
19 Correct 75 ms 192852 KB Output is correct
20 Correct 1847 ms 194516 KB Output is correct
21 Correct 1399 ms 194508 KB Output is correct
22 Correct 1642 ms 194508 KB Output is correct
23 Correct 1772 ms 194504 KB Output is correct
24 Correct 1759 ms 194548 KB Output is correct
25 Correct 1895 ms 194508 KB Output is correct
26 Correct 1896 ms 194504 KB Output is correct
27 Correct 1897 ms 194504 KB Output is correct
28 Correct 1800 ms 194508 KB Output is correct
29 Correct 955 ms 194496 KB Output is correct
30 Correct 1883 ms 194504 KB Output is correct
31 Correct 1959 ms 194476 KB Output is correct
32 Correct 1974 ms 194560 KB Output is correct
33 Correct 1816 ms 194508 KB Output is correct
34 Correct 779 ms 194456 KB Output is correct
35 Correct 1886 ms 194508 KB Output is correct
36 Correct 1854 ms 194684 KB Output is correct
37 Correct 1481 ms 194672 KB Output is correct
38 Correct 1654 ms 194508 KB Output is correct
39 Correct 1782 ms 194504 KB Output is correct
40 Correct 1750 ms 194504 KB Output is correct
41 Correct 1822 ms 194508 KB Output is correct
42 Correct 1907 ms 194508 KB Output is correct
43 Correct 1980 ms 194504 KB Output is correct
44 Correct 1819 ms 194672 KB Output is correct
45 Correct 1056 ms 194504 KB Output is correct
46 Correct 2113 ms 194504 KB Output is correct
47 Correct 1993 ms 194504 KB Output is correct
48 Correct 2153 ms 194504 KB Output is correct
49 Correct 2025 ms 194504 KB Output is correct
50 Correct 788 ms 194504 KB Output is correct
51 Correct 2070 ms 194516 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 192884 KB Output is correct
2 Correct 76 ms 192932 KB Output is correct
3 Correct 76 ms 192964 KB Output is correct
4 Correct 76 ms 192852 KB Output is correct
5 Correct 77 ms 192852 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 76 ms 192884 KB Output is correct
8 Correct 77 ms 192852 KB Output is correct
9 Correct 81 ms 192800 KB Output is correct
10 Correct 82 ms 192848 KB Output is correct
11 Correct 81 ms 192804 KB Output is correct
12 Correct 80 ms 192984 KB Output is correct
13 Correct 78 ms 192856 KB Output is correct
14 Correct 81 ms 192848 KB Output is correct
15 Correct 81 ms 192912 KB Output is correct
16 Correct 76 ms 192848 KB Output is correct
17 Correct 75 ms 192852 KB Output is correct
18 Correct 87 ms 192940 KB Output is correct
19 Correct 75 ms 192852 KB Output is correct
20 Correct 1847 ms 194516 KB Output is correct
21 Correct 1399 ms 194508 KB Output is correct
22 Correct 1642 ms 194508 KB Output is correct
23 Correct 1772 ms 194504 KB Output is correct
24 Correct 1759 ms 194548 KB Output is correct
25 Correct 1895 ms 194508 KB Output is correct
26 Correct 1896 ms 194504 KB Output is correct
27 Correct 1897 ms 194504 KB Output is correct
28 Correct 1800 ms 194508 KB Output is correct
29 Correct 955 ms 194496 KB Output is correct
30 Correct 1883 ms 194504 KB Output is correct
31 Correct 1959 ms 194476 KB Output is correct
32 Correct 1974 ms 194560 KB Output is correct
33 Correct 1816 ms 194508 KB Output is correct
34 Correct 779 ms 194456 KB Output is correct
35 Correct 1886 ms 194508 KB Output is correct
36 Correct 79 ms 192924 KB Output is correct
37 Correct 80 ms 192996 KB Output is correct
38 Correct 78 ms 192852 KB Output is correct
39 Runtime error 1898 ms 394916 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -