oj.uz

Submission #252371

# Submission time Handle Problem Language Result Execution time Memory
252371 2020-07-25T11:59:00 Z khangal Bridges (APIO19_bridges) C++14
27 / 100
 558 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-1){
        ll mid=(l+r)/2;
        if(query(1,1,n,node,mid-1)>=val)l=mid;
        else r=mid;
    }
    ll x = l - node;
    l = 1,r = node;
    while(l < r-1){
        ll mid=(l+r)/2;
        if(query(1,1,n,mid,node-1)>=val)r=mid;
        else l=mid;
    }
    ll y = node - 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,m);
            //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 101 ms 197496 KB Output is correct
2 Correct 104 ms 197496 KB Output is correct
3 Correct 187 ms 197624 KB Output is correct
4 Correct 131 ms 197624 KB Output is correct
5 Correct 127 ms 197496 KB Output is correct
6 Correct 124 ms 197516 KB Output is correct
7 Correct 133 ms 197496 KB Output is correct
8 Correct 147 ms 197496 KB Output is correct
9 Correct 137 ms 197496 KB Output is correct
10 Correct 134 ms 197496 KB Output is correct
11 Correct 137 ms 197472 KB Output is correct
12 Correct 143 ms 197496 KB Output is correct
13 Correct 142 ms 197496 KB Output is correct
14 Correct 141 ms 197496 KB Output is correct
15 Correct 142 ms 197496 KB Output is correct
16 Correct 136 ms 197500 KB Output is correct
17 Correct 134 ms 197616 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 523 ms 201568 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 409 ms 209288 KB Output is correct
2 Correct 430 ms 197724 KB Output is correct
3 Correct 243 ms 203332 KB Output is correct
4 Correct 268 ms 203372 KB Output is correct
5 Correct 326 ms 209256 KB Output is correct
6 Correct 401 ms 209384 KB Output is correct
7 Correct 344 ms 209464 KB Output is correct
8 Correct 322 ms 208232 KB Output is correct
9 Correct 321 ms 208104 KB Output is correct
10 Correct 312 ms 208328 KB Output is correct
11 Correct 357 ms 208784 KB Output is correct
12 Correct 356 ms 208744 KB Output is correct
13 Correct 347 ms 208872 KB Output is correct
14 Correct 324 ms 209256 KB Output is correct
15 Correct 328 ms 209256 KB Output is correct
16 Correct 416 ms 209320 KB Output is correct
17 Correct 394 ms 209256 KB Output is correct
18 Correct 408 ms 209512 KB Output is correct
19 Correct 395 ms 209260 KB Output is correct
20 Correct 365 ms 208972 KB Output is correct
21 Correct 365 ms 209000 KB Output is correct
22 Correct 398 ms 209256 KB Output is correct
23 Correct 322 ms 208872 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 197496 KB Output is correct
2 Correct 104 ms 197496 KB Output is correct
3 Correct 187 ms 197624 KB Output is correct
4 Correct 131 ms 197624 KB Output is correct
5 Correct 127 ms 197496 KB Output is correct
6 Correct 124 ms 197516 KB Output is correct
7 Correct 133 ms 197496 KB Output is correct
8 Correct 147 ms 197496 KB Output is correct
9 Correct 137 ms 197496 KB Output is correct
10 Correct 134 ms 197496 KB Output is correct
11 Correct 137 ms 197472 KB Output is correct
12 Correct 143 ms 197496 KB Output is correct
13 Correct 142 ms 197496 KB Output is correct
14 Correct 141 ms 197496 KB Output is correct
15 Correct 142 ms 197496 KB Output is correct
16 Correct 136 ms 197500 KB Output is correct
17 Correct 134 ms 197616 KB Output is correct
18 Incorrect 558 ms 202616 KB Output isn't correct
19 Halted 0 ms 0 KB -