oj.uz

Submission #252315

# Submission time Handle Problem Language Result Execution time Memory
252315 2020-07-25T08:57:18 Z khangal Bridges (APIO19_bridges) C++14
27 / 100
 425 ms 209764 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long , long long > pl;
const int N=1e6+1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,x,y,r,z,h,a[1234567],w;
bool used[1234567],used1[1234567];
pl p[1234567];
string s,s1[1234567];
map<ll,ll> mp;
map<pl,ll> mpl;
vector<pl> vec,vec1,ansvec;
vector<ll> v[1234567],v1[1234567];
vector<ll> vp[1234567];
set<ll> st;
stack <ll> sta;
set<ll> c1[1234][1234];
void dfs(ll x){
    used[x]=1;
    ans++;
    for(auto u:v[x]){
        if(used[u]==0)dfs(u);
    }
}
ll solve(ll x){
    if(x==c[x])return x;
    else return c[x] = solve(c[x]);
}
int main(){
    cin>>n>>m;
    rep(i,1,m){
        cin>>x>>y>>z;
        a[i]=x;
        b[i]=y;
        e[i]=z;
    }
    cin>>k;
    if(n<=1000&&m<=1000&&k<=100000){
        rep(i,1,k){
            ll q;
            cin>>q;
            if(q==1){
                cin>>l>>r;
                e[l]=r;
            }
            else{
                cin>>l>>r;
                rep(j,1,m)v[j].clear(),used[j]=0;
                // rep(j,1,m)cout<<e[j]<<" ";
                // cout<<'\n';
                rep(j,1,m){
                    if(e[j]>=r)v[a[j]].pb(b[j]),v[b[j]].pb(a[j]);
                }
                ans=0;
                dfs(l);
                cout<<ans<<'\n';
            }
        }
    }
    else{
        rep(i,1,n)c[i]=i,d[i]=1;
        vector<pair<ll,pl>> vpl;
        rep(i,1,m){
            vpl.pb({e[i],{a[i],b[i]}});
        }
        rep(i,1,k){
            cin>>x>>y>>z;
            vpl.pb({z,{-y,-i}});
        }
        sort(vpl.rbegin(),vpl.rend());
        rep(i,0,vpl.size()-1){
            if(vpl[i].ss.ss<0){
                x = -vpl[i].ss.ss;
                y = -vpl[i].ss.ff;
                e[x] = d[solve(y)];
            }
            else{
                y = vpl[i].ss.ss;
                x = vpl[i].ss.ff;
                x = solve(x);
                y = solve(y);
                if(x!=y){
                    d[x]+=d[y];
                    c[y]=x;
                }
            }
        }
        rep(i,1,k)cout<<e[i]<<"\n";
    }
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:22:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(ll i=a;i<=b;i++)
bridges.cpp:95:13:
         rep(i,0,vpl.size()-1){
             ~~~~~~~~~~~~~~~~    
bridges.cpp:95:9: note: in expansion of macro 'rep'
         rep(i,0,vpl.size()-1){
         ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 197496 KB Output is correct
2 Correct 138 ms 197500 KB Output is correct
3 Correct 202 ms 197752 KB Output is correct
4 Correct 146 ms 197624 KB Output is correct
5 Correct 141 ms 197624 KB Output is correct
6 Correct 143 ms 197624 KB Output is correct
7 Correct 139 ms 197624 KB Output is correct
8 Correct 130 ms 197624 KB Output is correct
9 Correct 142 ms 197624 KB Output is correct
10 Correct 129 ms 197624 KB Output is correct
11 Correct 133 ms 197624 KB Output is correct
12 Correct 128 ms 197624 KB Output is correct
13 Correct 134 ms 197624 KB Output is correct
14 Correct 132 ms 197752 KB Output is correct
15 Correct 134 ms 197624 KB Output is correct
16 Correct 127 ms 197624 KB Output is correct
17 Correct 143 ms 197624 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 207456 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 423 ms 209764 KB Output is correct
2 Correct 411 ms 199096 KB Output is correct
3 Correct 249 ms 204908 KB Output is correct
4 Correct 256 ms 205036 KB Output is correct
5 Correct 397 ms 208740 KB Output is correct
6 Correct 421 ms 209760 KB Output is correct
7 Correct 332 ms 208740 KB Output is correct
8 Correct 326 ms 208392 KB Output is correct
9 Correct 394 ms 208480 KB Output is correct
10 Correct 352 ms 208356 KB Output is correct
11 Correct 387 ms 209124 KB Output is correct
12 Correct 374 ms 209252 KB Output is correct
13 Correct 355 ms 208864 KB Output is correct
14 Correct 335 ms 208740 KB Output is correct
15 Correct 333 ms 208676 KB Output is correct
16 Correct 415 ms 209764 KB Output is correct
17 Correct 421 ms 209760 KB Output is correct
18 Correct 412 ms 209764 KB Output is correct
19 Correct 420 ms 209764 KB Output is correct
20 Correct 365 ms 209124 KB Output is correct
21 Correct 366 ms 209120 KB Output is correct
22 Correct 425 ms 209508 KB Output is correct
23 Correct 338 ms 208356 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 197496 KB Output is correct
2 Correct 138 ms 197500 KB Output is correct
3 Correct 202 ms 197752 KB Output is correct
4 Correct 146 ms 197624 KB Output is correct
5 Correct 141 ms 197624 KB Output is correct
6 Correct 143 ms 197624 KB Output is correct
7 Correct 139 ms 197624 KB Output is correct
8 Correct 130 ms 197624 KB Output is correct
9 Correct 142 ms 197624 KB Output is correct
10 Correct 129 ms 197624 KB Output is correct
11 Correct 133 ms 197624 KB Output is correct
12 Correct 128 ms 197624 KB Output is correct
13 Correct 134 ms 197624 KB Output is correct
14 Correct 132 ms 197752 KB Output is correct
15 Correct 134 ms 197624 KB Output is correct
16 Correct 127 ms 197624 KB Output is correct
17 Correct 143 ms 197624 KB Output is correct
18 Incorrect 330 ms 208384 KB Output isn't correct
19 Halted 0 ms 0 KB -