oj.uz

답안 #1035259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035259 2024-07-26T08:06:03 Z shenfe1 Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 695 ms 205124 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[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

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 98900 KB Output is correct
2 Correct 38 ms 99020 KB Output is correct
3 Correct 39 ms 98908 KB Output is correct
4 Correct 41 ms 98900 KB Output is correct
5 Correct 38 ms 98896 KB Output is correct
6 Correct 38 ms 98900 KB Output is correct
7 Correct 37 ms 98940 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 37 ms 98896 KB Output is correct
10 Correct 37 ms 98908 KB Output is correct
11 Correct 41 ms 98896 KB Output is correct
12 Correct 38 ms 98900 KB Output is correct
13 Correct 37 ms 98900 KB Output is correct
14 Correct 36 ms 98928 KB Output is correct
15 Correct 38 ms 98900 KB Output is correct
16 Correct 38 ms 98900 KB Output is correct
17 Correct 39 ms 98900 KB Output is correct
18 Correct 41 ms 99068 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 98900 KB Output is correct
2 Correct 38 ms 99020 KB Output is correct
3 Correct 39 ms 98908 KB Output is correct
4 Correct 41 ms 98900 KB Output is correct
5 Correct 38 ms 98896 KB Output is correct
6 Correct 38 ms 98900 KB Output is correct
7 Correct 37 ms 98940 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 37 ms 98896 KB Output is correct
10 Correct 37 ms 98908 KB Output is correct
11 Correct 41 ms 98896 KB Output is correct
12 Correct 38 ms 98900 KB Output is correct
13 Correct 37 ms 98900 KB Output is correct
14 Correct 36 ms 98928 KB Output is correct
15 Correct 38 ms 98900 KB Output is correct
16 Correct 38 ms 98900 KB Output is correct
17 Correct 39 ms 98900 KB Output is correct
18 Correct 41 ms 99068 KB Output is correct
19 Correct 37 ms 98900 KB Output is correct
20 Runtime error 695 ms 204768 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 98904 KB Output is correct
2 Correct 37 ms 98896 KB Output is correct
3 Correct 37 ms 98904 KB Output is correct
4 Runtime error 614 ms 205124 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 98900 KB Output is correct
2 Correct 38 ms 99020 KB Output is correct
3 Correct 39 ms 98908 KB Output is correct
4 Correct 41 ms 98900 KB Output is correct
5 Correct 38 ms 98896 KB Output is correct
6 Correct 38 ms 98900 KB Output is correct
7 Correct 37 ms 98940 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 37 ms 98896 KB Output is correct
10 Correct 37 ms 98908 KB Output is correct
11 Correct 41 ms 98896 KB Output is correct
12 Correct 38 ms 98900 KB Output is correct
13 Correct 37 ms 98900 KB Output is correct
14 Correct 36 ms 98928 KB Output is correct
15 Correct 38 ms 98900 KB Output is correct
16 Correct 38 ms 98900 KB Output is correct
17 Correct 39 ms 98900 KB Output is correct
18 Correct 41 ms 99068 KB Output is correct
19 Correct 38 ms 98900 KB Output is correct
20 Runtime error 198 ms 204112 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 98900 KB Output is correct
2 Correct 38 ms 99020 KB Output is correct
3 Correct 39 ms 98908 KB Output is correct
4 Correct 41 ms 98900 KB Output is correct
5 Correct 38 ms 98896 KB Output is correct
6 Correct 38 ms 98900 KB Output is correct
7 Correct 37 ms 98940 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 37 ms 98896 KB Output is correct
10 Correct 37 ms 98908 KB Output is correct
11 Correct 41 ms 98896 KB Output is correct
12 Correct 38 ms 98900 KB Output is correct
13 Correct 37 ms 98900 KB Output is correct
14 Correct 36 ms 98928 KB Output is correct
15 Correct 38 ms 98900 KB Output is correct
16 Correct 38 ms 98900 KB Output is correct
17 Correct 39 ms 98900 KB Output is correct
18 Correct 41 ms 99068 KB Output is correct
19 Correct 37 ms 98900 KB Output is correct
20 Runtime error 695 ms 204768 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 98900 KB Output is correct
2 Correct 38 ms 99020 KB Output is correct
3 Correct 39 ms 98908 KB Output is correct
4 Correct 41 ms 98900 KB Output is correct
5 Correct 38 ms 98896 KB Output is correct
6 Correct 38 ms 98900 KB Output is correct
7 Correct 37 ms 98940 KB Output is correct
8 Correct 38 ms 98896 KB Output is correct
9 Correct 37 ms 98896 KB Output is correct
10 Correct 37 ms 98908 KB Output is correct
11 Correct 41 ms 98896 KB Output is correct
12 Correct 38 ms 98900 KB Output is correct
13 Correct 37 ms 98900 KB Output is correct
14 Correct 36 ms 98928 KB Output is correct
15 Correct 38 ms 98900 KB Output is correct
16 Correct 38 ms 98900 KB Output is correct
17 Correct 39 ms 98900 KB Output is correct
18 Correct 41 ms 99068 KB Output is correct
19 Correct 37 ms 98900 KB Output is correct
20 Runtime error 695 ms 204768 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -