Submission #252378

#	Time	Username	Problem	Language	Result	Execution time	Memory
252378		khangal	Bridges (APIO19_bridges)	C++14	43 / 100	826 ms	209384 KiB

bridges

#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,h,a[1234567],w;
ll x[1234567],y[1234567],z[1234567];
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];
ll tr[1234567];
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]);
}
void build(ll node,ll l,ll r){
    if(l==r){
        tr[node]=e[l];
        return;
    }
    ll mid=(l+r)/2;
    build(node*2 , l , mid);
    build(node*2+1 , mid+1 , r);
    tr[node] = min(tr[node*2] , tr[node*2+1]);
}
void update(ll node,ll l,ll r,ll k,ll val){
    if(l == r){
        tr[node]=val;
        return;
    }
    ll mid = (l+r)/2;
    if(k <= mid) update(node*2,l,mid,k,val);
    else update(node*2+1,mid+1,r,k,val);
    tr[node] = min(tr[node*2],tr[node*2+1]);
}
ll query(ll node,ll l,ll r,ll L,ll R){
    if(L <= l && R >= r) return tr[node];
    ll mid = (l+r)/2;
    if(L <= mid && R > mid){
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    if(L <= mid) return query(node*2,l,mid,L,R);
    return query(node*2+1,mid+1,r,L,R);
}
ll solve(ll x,ll y){
    int lo = x, hi = m;
            while (lo < hi) {
                int mid = (lo + hi + 1)/2;
                if (query(1,1,m,x,mid) >= y)
                    lo = mid;
                else hi = mid-1;
            }
            int ans = 1;
            if (x != n && query(1,1,m,lo,lo) < y) lo--;
            if (x != n) ans += lo + 1 - x;
            lo = 1, hi = x-1;
            if (x != 1) {
            while (lo < hi) {
                int mid = (lo + hi)/2;
                if (query(1,1,m,mid,x-1) >= y)
                    hi = mid;
                else lo = mid+1;
            }
            if (hi == 0 || query(1,1,m,hi,x-1) < y) hi++;
            ans += x - hi;
            }
            return ans;
}
int main(){
    cin>>n>>m;
    rep(i,1,m){
        ll x,y,z;
        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){
                ll l,r;
                cin>>l>>r;
                e[l]=r;
            }
            else{
                ll l,r;
                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{
        ll q=0;
        rep(i,1,k)cin>>x[i]>>y[i]>>z[i],q+=(x[i]==1);
        if(q==0){
            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){
                vpl.pb({z[i],{-y[i],-i}});
            }
            sort(vpl.rbegin(),vpl.rend());
            rep(i,0,vpl.size()-1){
                if(vpl[i].ss.ss<0){
                    ll x = -vpl[i].ss.ss;
                    ll y = -vpl[i].ss.ff;
                    e[x] = d[solve(y)];
                }
                else{
                    ll y = vpl[i].ss.ss;
                    ll 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";
        }
        else{
            rep(i,m+1,2*n)e[i]=MAX;
            build(1,1,m);
            //rep(i,1,2*n)cout<<tr[i]<<" ";   
            rep(i,1,k){
                if(x[i]==1){
                    update(1,1,m,y[i],z[i]);
                }
                else{
                    cout<<solve(y[i],z[i])<<'\n';
                }
            }
        }
    }
}

Compilation message (stderr)

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:155:17:
             rep(i,0,vpl.size()-1){
                 ~~~~~~~~~~~~~~~~
bridges.cpp:155:13: note: in expansion of macro 'rep'
             rep(i,0,vpl.size()-1){
             ^~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27