oj.uz

Submission #965050

# Submission time Handle Problem Language Result Execution time Memory
965050 2024-04-18T04:21:50 Z irmuun Bridges (APIO19_bridges) C++17
14 / 100
 96 ms 18648 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct dsu{
    ll n;
    vector<ll>par,sz;
    dsu(ll n):n(n){
        par.resize(n+1);
        iota(all(par),0);
        sz.resize(n+1);
        fill(all(sz),1);
    }
    ll find(ll x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    ll SZ(ll x){
        x=find(x);
        return sz[x];
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        return x==y;
    }
    void merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]) swap(x,y);
            sz[x]+=sz[y];
            par[y]=x;
        }
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    vector<pair<ll,ll>>adj[n+5];
    vector<array<ll,3>>edge;
    for(ll i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        edge.pb({w,v,u});
    }
    ll q;
    cin>>q;
    vector<array<ll,3>>que;
    vector<ll>ans(q);
    ll cur=0;
    while(q--){
        ll t;
        cin>>t;
        if(t==1){
            ll b,r;
            cin>>b>>r;
        }
        else{
            ll s,w;
            cin>>s>>w;
            que.pb({w,s,cur++});
        }
    }
    sort(rall(que));
    sort(rall(edge));
    ll l=0;
    dsu ds(n);
    for(auto [w,s,ind]:que){
        while(l<m&&edge[l][0]>=w){
            ds.merge(edge[l][1],edge[l][2]);
            l++;
        }
        ans[ind]=ds.SZ(s);
    }
    for(ll i=0;i<que.size();i++){
        cout<<ans[i]<<"\n";
    }
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:87:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(ll i=0;i<que.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 10660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 8640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18284 KB Output is correct
2 Correct 33 ms 5580 KB Output is correct
3 Correct 35 ms 9488 KB Output is correct
4 Correct 45 ms 10448 KB Output is correct
5 Correct 83 ms 16616 KB Output is correct
6 Correct 81 ms 18648 KB Output is correct
7 Correct 86 ms 17408 KB Output is correct
8 Correct 60 ms 12736 KB Output is correct
9 Correct 66 ms 12804 KB Output is correct
10 Correct 58 ms 12164 KB Output is correct
11 Correct 73 ms 16636 KB Output is correct
12 Correct 74 ms 16892 KB Output is correct
13 Correct 77 ms 16648 KB Output is correct
14 Correct 78 ms 17916 KB Output is correct
15 Correct 79 ms 17936 KB Output is correct
16 Correct 87 ms 18208 KB Output is correct
17 Correct 90 ms 17540 KB Output is correct
18 Correct 96 ms 18408 KB Output is correct
19 Correct 85 ms 18408 KB Output is correct
20 Correct 84 ms 16636 KB Output is correct
21 Correct 74 ms 16368 KB Output is correct
22 Correct 79 ms 17324 KB Output is correct
23 Correct 69 ms 15600 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 10660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -