oj.uz

Submission #1034119

# Submission time Handle Problem Language Result Execution time Memory
1034119 2024-07-25T09:53:40 Z shenfe1 Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 5000 ms 96380 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
 
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 int ll
 
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;

vector<int> L[MAX],R[MAX];
vector<pair<int,pii>> e;
 
ll solve(int d){
    int pos=lb(all(e),make_pair(d,make_pair(0,0)))-e.begin();
    int p1=0,p2=0;
    ll ans=0;
    D.init(n);
    // cerr<<sz(L[pos])<<" "<<sz(R[pos])<<"\n";
    // for(auto x:L[pos])cout<<e[x].F<<" "<<e[x].S.F<<" "<<e[x].S.S<<"\n";
    // for(auto x:R[pos])cout<<e[x].F<<" "<<e[x].S.F<<" "<<e[x].S.S<<"\n";
    for(int c=0;c<n-1;){
        if((p2<sz(R[pos])&&p1<sz(L[pos])&&d-e[L[pos][p1]].F<e[R[pos][p2]].F-d)||p2>=sz(R[pos])){
            if(D.get(e[L[pos][p1]].S.F)!=D.get(e[L[pos][p1]].S.S)){
                D.unite(e[L[pos][p1]].S.F,e[L[pos][p1]].S.S);
                ans+=d-e[L[pos][p1]].F;
                c++;
            }
            p1++;
        }
        else{
            if(D.get(e[R[pos][p2]].S.F)!=D.get(e[R[pos][p2]].S.S)){
                D.unite(e[R[pos][p2]].S.F,e[R[pos][p2]].S.S);
                ans+=e[R[pos][p2]].F-d;
                c++;
            }
            p2++;
        }
    }
    return ans;
}
 
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));
    for(int i=0;i<=m;i++){
        D.init(n);
        for(int j=i-1;j>=0;j--){
            if(D.get(e[j].S.F)!=D.get(e[j].S.S)){
                L[i].pb(j);
                D.unite(e[j].S.F,e[j].S.S);
            }
        }
    }
    for(int i=0;i<=m;i++){
        D.init(n);
        for(int j=i;j<m;j++){
            if(D.get(e[j].S.F)!=D.get(e[j].S.S)){
                R[i].pb(j);
                D.unite(e[j].S.F,e[j].S.S);
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int d;
        cin>>d;
        // solve(d);
        cout<<solve(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:117:9: warning: unused variable 'init' [-Wunused-variable]
  117 |     int init=clock();
      |         ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9772 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 7 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9768 KB Output is correct
17 Correct 4 ms 9652 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9772 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 7 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9768 KB Output is correct
17 Correct 4 ms 9652 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Execution timed out 5041 ms 94396 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Execution timed out 5089 ms 96380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9772 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 7 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9768 KB Output is correct
17 Correct 4 ms 9652 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9816 KB Output is correct
20 Execution timed out 5044 ms 23348 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9772 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 7 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9768 KB Output is correct
17 Correct 4 ms 9652 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Execution timed out 5041 ms 94396 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 5 ms 9772 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 7 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 10076 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9768 KB Output is correct
17 Correct 4 ms 9652 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Execution timed out 5041 ms 94396 KB Time limit exceeded
21 Halted 0 ms 0 KB -