oj.uz

Submission #252347

# Submission time Handle Problem Language Result Execution time Memory
252347 2020-07-25T10:55:44 Z khangal Bridges (APIO19_bridges) C++14
27 / 100
 3000 ms 209512 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,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 node,ll val){
    ll l = node,r = n;
    while(l<r){
        ll mid=(l+r+1)/2;
        if(query(1,1,n,node,mid)>=val)l=mid;
        else r=mid-1;
    }
    ll x = l;
    l = 1,r = node;
    while(l<r){
        ll mid=(l+r+1)/2;
        if(query(1,1,n,mid,node)>=val)r=mid;
        else l=mid+1;
    }
    ll y = r;
    return x-y+1;
}
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,n);
            //rep(i,1,2*n)cout<<tr[i]<<" ";   
            rep(i,1,k){
                if(x[i]==1){
                    update(1,1,n,y[i],z[i]);
                }
                else{
                    cout<<solve(y[i],z[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:148:17:
             rep(i,0,vpl.size()-1){
                 ~~~~~~~~~~~~~~~~
bridges.cpp:148:13: 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 111 ms 197496 KB Output is correct
2 Correct 100 ms 197496 KB Output is correct
3 Correct 198 ms 197764 KB Output is correct
4 Correct 128 ms 197496 KB Output is correct
5 Correct 129 ms 197624 KB Output is correct
6 Correct 125 ms 197496 KB Output is correct
7 Correct 125 ms 197484 KB Output is correct
8 Correct 125 ms 197496 KB Output is correct
9 Correct 130 ms 197624 KB Output is correct
10 Correct 124 ms 197496 KB Output is correct
11 Correct 124 ms 197496 KB Output is correct
12 Correct 126 ms 197496 KB Output is correct
13 Correct 133 ms 197496 KB Output is correct
14 Correct 130 ms 197496 KB Output is correct
15 Correct 134 ms 197496 KB Output is correct
16 Correct 124 ms 197496 KB Output is correct
17 Correct 124 ms 197800 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 202556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 201592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 209256 KB Output is correct
2 Correct 406 ms 197752 KB Output is correct
3 Correct 238 ms 203372 KB Output is correct
4 Correct 250 ms 203372 KB Output is correct
5 Correct 337 ms 209512 KB Output is correct
6 Correct 400 ms 209384 KB Output is correct
7 Correct 331 ms 209256 KB Output is correct
8 Correct 314 ms 208248 KB Output is correct
9 Correct 317 ms 208104 KB Output is correct
10 Correct 310 ms 208232 KB Output is correct
11 Correct 355 ms 208872 KB Output is correct
12 Correct 373 ms 208744 KB Output is correct
13 Correct 347 ms 208744 KB Output is correct
14 Correct 332 ms 209512 KB Output is correct
15 Correct 329 ms 209436 KB Output is correct
16 Correct 398 ms 209368 KB Output is correct
17 Correct 408 ms 209384 KB Output is correct
18 Correct 401 ms 209256 KB Output is correct
19 Correct 399 ms 209280 KB Output is correct
20 Correct 352 ms 208872 KB Output is correct
21 Correct 350 ms 208872 KB Output is correct
22 Correct 379 ms 209128 KB Output is correct
23 Correct 307 ms 208744 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 202556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 197496 KB Output is correct
2 Correct 100 ms 197496 KB Output is correct
3 Correct 198 ms 197764 KB Output is correct
4 Correct 128 ms 197496 KB Output is correct
5 Correct 129 ms 197624 KB Output is correct
6 Correct 125 ms 197496 KB Output is correct
7 Correct 125 ms 197484 KB Output is correct
8 Correct 125 ms 197496 KB Output is correct
9 Correct 130 ms 197624 KB Output is correct
10 Correct 124 ms 197496 KB Output is correct
11 Correct 124 ms 197496 KB Output is correct
12 Correct 126 ms 197496 KB Output is correct
13 Correct 133 ms 197496 KB Output is correct
14 Correct 130 ms 197496 KB Output is correct
15 Correct 134 ms 197496 KB Output is correct
16 Correct 124 ms 197496 KB Output is correct
17 Correct 124 ms 197800 KB Output is correct
18 Execution timed out 3090 ms 202556 KB Time limit exceeded
19 Halted 0 ms 0 KB -