oj.uz

Submission #1035265

# Submission time Handle Problem Language Result Execution time Memory
1035265 2024-07-26T08:15:19 Z shenfe1 Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 2197 ms 202740 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(pos<=tm){
            if(L[v])return t[v]+get(L[v],tl,tm,pos);
            return t[v];
        }
        else{
            if(R[v])return t[v]+get(R[v],tm+1,tr,pos);
            return t[v];
        }
    }
}T[2];

vector<pair<int,pii>> e;
set<pii> g[510];
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:179:9: warning: unused variable 'init' [-Wunused-variable]
  179 |     int init=clock();
      |         ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188244 KB Output is correct
2 Correct 76 ms 188244 KB Output is correct
3 Correct 73 ms 188288 KB Output is correct
4 Correct 73 ms 188208 KB Output is correct
5 Correct 67 ms 188240 KB Output is correct
6 Correct 71 ms 188172 KB Output is correct
7 Correct 74 ms 188240 KB Output is correct
8 Correct 70 ms 188192 KB Output is correct
9 Correct 67 ms 188240 KB Output is correct
10 Correct 71 ms 188244 KB Output is correct
11 Correct 73 ms 188304 KB Output is correct
12 Correct 74 ms 188096 KB Output is correct
13 Correct 70 ms 188240 KB Output is correct
14 Correct 74 ms 188136 KB Output is correct
15 Correct 72 ms 188212 KB Output is correct
16 Correct 69 ms 188244 KB Output is correct
17 Correct 71 ms 188244 KB Output is correct
18 Correct 70 ms 188244 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188244 KB Output is correct
2 Correct 76 ms 188244 KB Output is correct
3 Correct 73 ms 188288 KB Output is correct
4 Correct 73 ms 188208 KB Output is correct
5 Correct 67 ms 188240 KB Output is correct
6 Correct 71 ms 188172 KB Output is correct
7 Correct 74 ms 188240 KB Output is correct
8 Correct 70 ms 188192 KB Output is correct
9 Correct 67 ms 188240 KB Output is correct
10 Correct 71 ms 188244 KB Output is correct
11 Correct 73 ms 188304 KB Output is correct
12 Correct 74 ms 188096 KB Output is correct
13 Correct 70 ms 188240 KB Output is correct
14 Correct 74 ms 188136 KB Output is correct
15 Correct 72 ms 188212 KB Output is correct
16 Correct 69 ms 188244 KB Output is correct
17 Correct 71 ms 188244 KB Output is correct
18 Correct 70 ms 188244 KB Output is correct
19 Correct 72 ms 188128 KB Output is correct
20 Correct 1814 ms 189976 KB Output is correct
21 Correct 1381 ms 189896 KB Output is correct
22 Correct 1552 ms 189896 KB Output is correct
23 Correct 1777 ms 189900 KB Output is correct
24 Correct 1689 ms 189900 KB Output is correct
25 Correct 1954 ms 189900 KB Output is correct
26 Correct 2064 ms 189980 KB Output is correct
27 Correct 2033 ms 189956 KB Output is correct
28 Correct 1765 ms 189920 KB Output is correct
29 Correct 921 ms 189784 KB Output is correct
30 Correct 1900 ms 190012 KB Output is correct
31 Correct 1890 ms 189900 KB Output is correct
32 Correct 1896 ms 189896 KB Output is correct
33 Correct 1866 ms 189896 KB Output is correct
34 Correct 705 ms 189896 KB Output is correct
35 Correct 1930 ms 189796 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 188240 KB Output is correct
2 Correct 75 ms 188240 KB Output is correct
3 Correct 73 ms 188284 KB Output is correct
4 Correct 1908 ms 200692 KB Output is correct
5 Correct 1920 ms 200640 KB Output is correct
6 Correct 1931 ms 200704 KB Output is correct
7 Correct 1207 ms 202560 KB Output is correct
8 Correct 1157 ms 202696 KB Output is correct
9 Correct 1172 ms 202740 KB Output is correct
10 Correct 1797 ms 200688 KB Output is correct
11 Correct 1012 ms 202696 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188244 KB Output is correct
2 Correct 76 ms 188244 KB Output is correct
3 Correct 73 ms 188288 KB Output is correct
4 Correct 73 ms 188208 KB Output is correct
5 Correct 67 ms 188240 KB Output is correct
6 Correct 71 ms 188172 KB Output is correct
7 Correct 74 ms 188240 KB Output is correct
8 Correct 70 ms 188192 KB Output is correct
9 Correct 67 ms 188240 KB Output is correct
10 Correct 71 ms 188244 KB Output is correct
11 Correct 73 ms 188304 KB Output is correct
12 Correct 74 ms 188096 KB Output is correct
13 Correct 70 ms 188240 KB Output is correct
14 Correct 74 ms 188136 KB Output is correct
15 Correct 72 ms 188212 KB Output is correct
16 Correct 69 ms 188244 KB Output is correct
17 Correct 71 ms 188244 KB Output is correct
18 Correct 70 ms 188244 KB Output is correct
19 Correct 77 ms 188244 KB Output is correct
20 Correct 252 ms 200620 KB Output is correct
21 Correct 229 ms 200784 KB Output is correct
22 Correct 249 ms 200528 KB Output is correct
23 Correct 233 ms 200532 KB Output is correct
24 Correct 222 ms 200464 KB Output is correct
25 Correct 218 ms 200648 KB Output is correct
26 Correct 231 ms 200532 KB Output is correct
27 Correct 202 ms 200488 KB Output is correct
28 Correct 241 ms 200532 KB Output is correct
29 Correct 267 ms 200708 KB Output is correct
30 Correct 235 ms 200540 KB Output is correct
31 Correct 236 ms 200532 KB Output is correct
32 Correct 199 ms 201044 KB Output is correct
33 Correct 247 ms 200272 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188244 KB Output is correct
2 Correct 76 ms 188244 KB Output is correct
3 Correct 73 ms 188288 KB Output is correct
4 Correct 73 ms 188208 KB Output is correct
5 Correct 67 ms 188240 KB Output is correct
6 Correct 71 ms 188172 KB Output is correct
7 Correct 74 ms 188240 KB Output is correct
8 Correct 70 ms 188192 KB Output is correct
9 Correct 67 ms 188240 KB Output is correct
10 Correct 71 ms 188244 KB Output is correct
11 Correct 73 ms 188304 KB Output is correct
12 Correct 74 ms 188096 KB Output is correct
13 Correct 70 ms 188240 KB Output is correct
14 Correct 74 ms 188136 KB Output is correct
15 Correct 72 ms 188212 KB Output is correct
16 Correct 69 ms 188244 KB Output is correct
17 Correct 71 ms 188244 KB Output is correct
18 Correct 70 ms 188244 KB Output is correct
19 Correct 72 ms 188128 KB Output is correct
20 Correct 1814 ms 189976 KB Output is correct
21 Correct 1381 ms 189896 KB Output is correct
22 Correct 1552 ms 189896 KB Output is correct
23 Correct 1777 ms 189900 KB Output is correct
24 Correct 1689 ms 189900 KB Output is correct
25 Correct 1954 ms 189900 KB Output is correct
26 Correct 2064 ms 189980 KB Output is correct
27 Correct 2033 ms 189956 KB Output is correct
28 Correct 1765 ms 189920 KB Output is correct
29 Correct 921 ms 189784 KB Output is correct
30 Correct 1900 ms 190012 KB Output is correct
31 Correct 1890 ms 189900 KB Output is correct
32 Correct 1896 ms 189896 KB Output is correct
33 Correct 1866 ms 189896 KB Output is correct
34 Correct 705 ms 189896 KB Output is correct
35 Correct 1930 ms 189796 KB Output is correct
36 Correct 1881 ms 189904 KB Output is correct
37 Correct 1431 ms 189988 KB Output is correct
38 Correct 1631 ms 189896 KB Output is correct
39 Correct 1792 ms 189896 KB Output is correct
40 Correct 1787 ms 190020 KB Output is correct
41 Correct 1806 ms 189896 KB Output is correct
42 Correct 1914 ms 189900 KB Output is correct
43 Correct 1884 ms 189952 KB Output is correct
44 Correct 1710 ms 189988 KB Output is correct
45 Correct 951 ms 189900 KB Output is correct
46 Correct 1862 ms 189980 KB Output is correct
47 Correct 1877 ms 189920 KB Output is correct
48 Correct 1932 ms 189896 KB Output is correct
49 Correct 1824 ms 189900 KB Output is correct
50 Correct 723 ms 190152 KB Output is correct
51 Correct 1875 ms 190024 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188244 KB Output is correct
2 Correct 76 ms 188244 KB Output is correct
3 Correct 73 ms 188288 KB Output is correct
4 Correct 73 ms 188208 KB Output is correct
5 Correct 67 ms 188240 KB Output is correct
6 Correct 71 ms 188172 KB Output is correct
7 Correct 74 ms 188240 KB Output is correct
8 Correct 70 ms 188192 KB Output is correct
9 Correct 67 ms 188240 KB Output is correct
10 Correct 71 ms 188244 KB Output is correct
11 Correct 73 ms 188304 KB Output is correct
12 Correct 74 ms 188096 KB Output is correct
13 Correct 70 ms 188240 KB Output is correct
14 Correct 74 ms 188136 KB Output is correct
15 Correct 72 ms 188212 KB Output is correct
16 Correct 69 ms 188244 KB Output is correct
17 Correct 71 ms 188244 KB Output is correct
18 Correct 70 ms 188244 KB Output is correct
19 Correct 72 ms 188128 KB Output is correct
20 Correct 1814 ms 189976 KB Output is correct
21 Correct 1381 ms 189896 KB Output is correct
22 Correct 1552 ms 189896 KB Output is correct
23 Correct 1777 ms 189900 KB Output is correct
24 Correct 1689 ms 189900 KB Output is correct
25 Correct 1954 ms 189900 KB Output is correct
26 Correct 2064 ms 189980 KB Output is correct
27 Correct 2033 ms 189956 KB Output is correct
28 Correct 1765 ms 189920 KB Output is correct
29 Correct 921 ms 189784 KB Output is correct
30 Correct 1900 ms 190012 KB Output is correct
31 Correct 1890 ms 189900 KB Output is correct
32 Correct 1896 ms 189896 KB Output is correct
33 Correct 1866 ms 189896 KB Output is correct
34 Correct 705 ms 189896 KB Output is correct
35 Correct 1930 ms 189796 KB Output is correct
36 Correct 76 ms 188240 KB Output is correct
37 Correct 75 ms 188240 KB Output is correct
38 Correct 73 ms 188284 KB Output is correct
39 Correct 1908 ms 200692 KB Output is correct
40 Correct 1920 ms 200640 KB Output is correct
41 Correct 1931 ms 200704 KB Output is correct
42 Correct 1207 ms 202560 KB Output is correct
43 Correct 1157 ms 202696 KB Output is correct
44 Correct 1172 ms 202740 KB Output is correct
45 Correct 1797 ms 200688 KB Output is correct
46 Correct 1012 ms 202696 KB Output is correct
47 Correct 77 ms 188244 KB Output is correct
48 Correct 252 ms 200620 KB Output is correct
49 Correct 229 ms 200784 KB Output is correct
50 Correct 249 ms 200528 KB Output is correct
51 Correct 233 ms 200532 KB Output is correct
52 Correct 222 ms 200464 KB Output is correct
53 Correct 218 ms 200648 KB Output is correct
54 Correct 231 ms 200532 KB Output is correct
55 Correct 202 ms 200488 KB Output is correct
56 Correct 241 ms 200532 KB Output is correct
57 Correct 267 ms 200708 KB Output is correct
58 Correct 235 ms 200540 KB Output is correct
59 Correct 236 ms 200532 KB Output is correct
60 Correct 199 ms 201044 KB Output is correct
61 Correct 247 ms 200272 KB Output is correct
62 Correct 1881 ms 189904 KB Output is correct
63 Correct 1431 ms 189988 KB Output is correct
64 Correct 1631 ms 189896 KB Output is correct
65 Correct 1792 ms 189896 KB Output is correct
66 Correct 1787 ms 190020 KB Output is correct
67 Correct 1806 ms 189896 KB Output is correct
68 Correct 1914 ms 189900 KB Output is correct
69 Correct 1884 ms 189952 KB Output is correct
70 Correct 1710 ms 189988 KB Output is correct
71 Correct 951 ms 189900 KB Output is correct
72 Correct 1862 ms 189980 KB Output is correct
73 Correct 1877 ms 189920 KB Output is correct
74 Correct 1932 ms 189896 KB Output is correct
75 Correct 1824 ms 189900 KB Output is correct
76 Correct 723 ms 190152 KB Output is correct
77 Correct 1875 ms 190024 KB Output is correct
78 Correct 2158 ms 199660 KB Output is correct
79 Correct 1658 ms 201696 KB Output is correct
80 Correct 1887 ms 200728 KB Output is correct
81 Correct 1971 ms 200644 KB Output is correct
82 Correct 2140 ms 199592 KB Output is correct
83 Correct 2176 ms 199620 KB Output is correct
84 Correct 2194 ms 199656 KB Output is correct
85 Correct 2170 ms 199500 KB Output is correct
86 Correct 1941 ms 199652 KB Output is correct
87 Correct 1036 ms 201196 KB Output is correct
88 Correct 2129 ms 199656 KB Output is correct
89 Correct 2197 ms 199620 KB Output is correct
90 Correct 2073 ms 199496 KB Output is correct
91 Correct 2066 ms 199648 KB Output is correct
92 Correct 862 ms 202432 KB Output is correct
93 Correct 1978 ms 200640 KB Output is correct