oj.uz

답안 #252382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252382 2020-07-25T12:10:51 Z khangal 다리 (APIO19_bridges) C++14
43 / 100
 832 ms 209384 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 = m;
    while(l < r){
        ll mid = (l + r + 1)/2;
        if(query(1,1,m,node,mid) >= val)
            l = mid;
        else r = mid-1;
    }
    ll ans=1;
    if(node != n && query(1,1,m,l,l) < val) l--;
    if(node != n) ans += l + 1 - node;
    l = 1, r = node-1;
    if(node != 1){
    while(l < r){
        ll mid = (l + r)/2;
        if(query(1,1,m,mid,node-1) >= val)
            r = mid;
        else l = mid+1;
    }
    if(r == 0 || query(1,1,m,r,node-1) < val) r++;
    ans += node - r;
    }
    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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 197496 KB Output is correct
2 Correct 99 ms 197496 KB Output is correct
3 Correct 187 ms 197624 KB Output is correct
4 Correct 130 ms 197624 KB Output is correct
5 Correct 127 ms 197496 KB Output is correct
6 Correct 134 ms 197496 KB Output is correct
7 Correct 124 ms 197496 KB Output is correct
8 Correct 129 ms 197496 KB Output is correct
9 Correct 134 ms 197496 KB Output is correct
10 Correct 125 ms 197496 KB Output is correct
11 Correct 124 ms 197496 KB Output is correct
12 Correct 124 ms 197496 KB Output is correct
13 Correct 130 ms 197496 KB Output is correct
14 Correct 132 ms 197496 KB Output is correct
15 Correct 132 ms 197624 KB Output is correct
16 Correct 125 ms 197496 KB Output is correct
17 Correct 123 ms 197496 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 579 ms 202528 KB Output is correct
2 Correct 559 ms 202656 KB Output is correct
3 Correct 560 ms 202744 KB Output is correct
4 Correct 563 ms 202616 KB Output is correct
5 Correct 562 ms 202616 KB Output is correct
6 Correct 589 ms 202872 KB Output is correct
7 Correct 608 ms 202744 KB Output is correct
8 Correct 596 ms 202744 KB Output is correct
9 Correct 393 ms 197624 KB Output is correct
10 Correct 535 ms 202644 KB Output is correct
11 Correct 531 ms 202616 KB Output is correct
12 Correct 832 ms 203004 KB Output is correct
13 Correct 369 ms 202616 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 519 ms 201612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 416 ms 209384 KB Output is correct
2 Correct 407 ms 197752 KB Output is correct
3 Correct 243 ms 203372 KB Output is correct
4 Correct 258 ms 203372 KB Output is correct
5 Correct 334 ms 209256 KB Output is correct
6 Correct 402 ms 209384 KB Output is correct
7 Correct 342 ms 209256 KB Output is correct
8 Correct 321 ms 208232 KB Output is correct
9 Correct 329 ms 208104 KB Output is correct
10 Correct 310 ms 208220 KB Output is correct
11 Correct 356 ms 208744 KB Output is correct
12 Correct 363 ms 208744 KB Output is correct
13 Correct 354 ms 208744 KB Output is correct
14 Correct 326 ms 209256 KB Output is correct
15 Correct 328 ms 209384 KB Output is correct
16 Correct 394 ms 209256 KB Output is correct
17 Correct 396 ms 209316 KB Output is correct
18 Correct 398 ms 209256 KB Output is correct
19 Correct 401 ms 209332 KB Output is correct
20 Correct 354 ms 208872 KB Output is correct
21 Correct 356 ms 209000 KB Output is correct
22 Correct 394 ms 209128 KB Output is correct
23 Correct 310 ms 208744 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 579 ms 202528 KB Output is correct
2 Correct 559 ms 202656 KB Output is correct
3 Correct 560 ms 202744 KB Output is correct
4 Correct 563 ms 202616 KB Output is correct
5 Correct 562 ms 202616 KB Output is correct
6 Correct 589 ms 202872 KB Output is correct
7 Correct 608 ms 202744 KB Output is correct
8 Correct 596 ms 202744 KB Output is correct
9 Correct 393 ms 197624 KB Output is correct
10 Correct 535 ms 202644 KB Output is correct
11 Correct 531 ms 202616 KB Output is correct
12 Correct 832 ms 203004 KB Output is correct
13 Correct 369 ms 202616 KB Output is correct
14 Incorrect 519 ms 201612 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 197496 KB Output is correct
2 Correct 99 ms 197496 KB Output is correct
3 Correct 187 ms 197624 KB Output is correct
4 Correct 130 ms 197624 KB Output is correct
5 Correct 127 ms 197496 KB Output is correct
6 Correct 134 ms 197496 KB Output is correct
7 Correct 124 ms 197496 KB Output is correct
8 Correct 129 ms 197496 KB Output is correct
9 Correct 134 ms 197496 KB Output is correct
10 Correct 125 ms 197496 KB Output is correct
11 Correct 124 ms 197496 KB Output is correct
12 Correct 124 ms 197496 KB Output is correct
13 Correct 130 ms 197496 KB Output is correct
14 Correct 132 ms 197496 KB Output is correct
15 Correct 132 ms 197624 KB Output is correct
16 Correct 125 ms 197496 KB Output is correct
17 Correct 123 ms 197496 KB Output is correct
18 Correct 579 ms 202528 KB Output is correct
19 Correct 559 ms 202656 KB Output is correct
20 Correct 560 ms 202744 KB Output is correct
21 Correct 563 ms 202616 KB Output is correct
22 Correct 562 ms 202616 KB Output is correct
23 Correct 589 ms 202872 KB Output is correct
24 Correct 608 ms 202744 KB Output is correct
25 Correct 596 ms 202744 KB Output is correct
26 Correct 393 ms 197624 KB Output is correct
27 Correct 535 ms 202644 KB Output is correct
28 Correct 531 ms 202616 KB Output is correct
29 Correct 832 ms 203004 KB Output is correct
30 Correct 369 ms 202616 KB Output is correct
31 Incorrect 519 ms 201612 KB Output isn't correct
32 Halted 0 ms 0 KB -