oj.uz

Submission #231691

# Submission time Handle Problem Language Result Execution time Memory
231691 2020-05-14T12:56:55 Z rrrr10000 Bridges (APIO19_bridges) C++14
59 / 100
 3000 ms 24196 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
vi dx={0,0,1,-1},dy={1,-1,0,0};
vector<PP> change;
vi parent,rankk,sz;
void init(ll n){
    parent=vi(n);
    rankk=vi(n);
    sz=vi(n,1);
    rep(i,n)parent[i]=i;
}
ll root(ll i){if(parent[i]==i)return i;return root(parent[i]);}
ll getsize(ll i){return sz[root(i)];}
bool same(ll a,ll b){return root(a)==root(b);}
bool heigou(ll x,ll y){
    x=root(x);y=root(y);
    if(x==y)return false;
    if(rankk[x]<rankk[y]){parent[x]=y;sz[y]+=sz[x];}
    else{parent[y]=x;sz[x]+=sz[y];}
    if(rankk[x]==rankk[y])rankk[x]++;
    return true;
}
bool heigou2(ll x,ll y){
    x=root(x);y=root(y);
    if(x==y)return false;
    if(rankk[x]<rankk[y]){
        change.pb(0,x,parent[x]);
        change.pb(2,y,sz[y]);
        parent[x]=y;sz[y]+=sz[x];
    }
    else{
        change.pb(0,y,parent[y]);
        change.pb(2,x,sz[x]);
        parent[y]=x;sz[x]+=sz[y];
    }
    if(rankk[x]==rankk[y]){
        change.pb(1,x,rankk[x]);
        rankk[x]++;
    }
    return true;
}
void maku(){
    while(change.size()){
        ll id,a,b;
        tie(id,a,b)=change.back();
        change.pop_back();
        if(id==0)parent[a]=b;
        if(id==1)rankk[a]=b;
        if(id==2)sz[a]=b;
    }
}
int main(){
    ll n,m,q;cin>>n>>m;
    vp ans;
    vp hen(m);
    vvp upd(m,vp(1));
    set<P> con;
    vi num(m);
    rep(i,m){
        cin>>hen[i].fi>>hen[i].se>>upd[i][0].se;
        hen[i].fi--;hen[i].se--;
        upd[i][0].fi=-1;
        upd[i][0].se*=-1;
        con.insert(P(upd[i][0].se,i));
        num[i]=upd[i][0].se;
    }
    cin>>q;
    ll block=550;
    vector<vector<PP>> group(q);
    ll cnt=-1;
    rep(i,q){
        ll t,a,b;cin>>t>>a>>b;b*=-1;
        t--;a--;
        if(i%block==0)cnt++;
        group[cnt].eb(t,a,b);
        if(!t)upd[a].eb(i,b);
    }
    cnt++;
    rep(i,cnt){
        init(n);
        vp s;
        rep(j,group[i].size()){
            if(get<0>(group[i][j]))s.eb(get<2>(group[i][j]),j);
            else{
                ll k=get<1>(group[i][j]);
                if(num[k]!=inf){
                    con.erase(P(num[k],k));
                    num[k]=inf;
                }
            }
        }
        auto itr=con.begin();
        int w=0;
        sort(all(s));
        while(itr!=con.end()){
            auto x=*itr;
            while(w<s.size()){
                if(x.fi<=s[w].fi)break;
                ll id=s[w].se,ma=s[w].fi;
                rep(j,group[i].size()){
                    if(get<0>(group[i][j]))continue;
                    ll it=lb(upd[get<1>(group[i][j])],P(i*block+id,-inf));
                    if(it&&upd[get<1>(group[i][j])][it-1].se<=ma)heigou2(hen[get<1>(group[i][j])].fi,hen[get<1>(group[i][j])].se);
                }
                ans.pb(i*block+id,getsize(get<1>(group[i][id])));
                maku();
                w++;
            }
            if(w==s.size())break;
            heigou(hen[x.se].fi,hen[x.se].se);
            itr++;
        }
        while(w<s.size()){
            ll id=s[w].se,ma=s[w].fi;
            rep(j,group[i].size()){
                if(get<0>(group[i][j]))continue;
                ll it=lb(upd[get<1>(group[i][j])],P(i*block+id,-inf));
                if(it&&upd[get<1>(group[i][j])][it-1].se<=ma)heigou2(hen[get<1>(group[i][j])].fi,hen[get<1>(group[i][j])].se);
            }
            ans.pb(i*block+id,getsize(get<1>(group[i][id])));
            maku();
            w++;
        }
        for(int j=group[i].size()-1;j>=0;j--){
            if(!get<0>(group[i][j])){
                ll k=get<1>(group[i][j]);
                if(num[k]==inf){
                    num[k]=get<2>(group[i][j]);
                    con.insert(P(num[k],k));
                }
            }
        }
    }
    sort(all(ans));
    for(auto x:ans)out(x.se);
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(w<s.size()){
                   ~^~~~~~~~~
bridges.cpp:159:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(w==s.size())break;
                ~^~~~~~~~~~
bridges.cpp:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(w<s.size()){
               ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 71 ms 1528 KB Output is correct
4 Correct 26 ms 1408 KB Output is correct
5 Correct 94 ms 1400 KB Output is correct
6 Correct 81 ms 1400 KB Output is correct
7 Correct 86 ms 1272 KB Output is correct
8 Correct 94 ms 1400 KB Output is correct
9 Correct 87 ms 1272 KB Output is correct
10 Correct 97 ms 1400 KB Output is correct
11 Correct 95 ms 1400 KB Output is correct
12 Correct 104 ms 1400 KB Output is correct
13 Correct 100 ms 1528 KB Output is correct
14 Correct 95 ms 1400 KB Output is correct
15 Correct 98 ms 1404 KB Output is correct
16 Correct 97 ms 1272 KB Output is correct
17 Correct 89 ms 1272 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2728 ms 17184 KB Output is correct
2 Correct 2492 ms 17356 KB Output is correct
3 Correct 2553 ms 17212 KB Output is correct
4 Correct 2645 ms 17424 KB Output is correct
5 Correct 2503 ms 17264 KB Output is correct
6 Correct 2663 ms 17520 KB Output is correct
7 Correct 2838 ms 17140 KB Output is correct
8 Correct 2986 ms 17428 KB Output is correct
9 Correct 207 ms 8164 KB Output is correct
10 Correct 1561 ms 17420 KB Output is correct
11 Correct 1555 ms 17408 KB Output is correct
12 Correct 1921 ms 17232 KB Output is correct
13 Correct 2075 ms 17768 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 14168 KB Output is correct
2 Correct 1146 ms 9972 KB Output is correct
3 Correct 1866 ms 14300 KB Output is correct
4 Correct 1657 ms 14148 KB Output is correct
5 Correct 213 ms 8164 KB Output is correct
6 Correct 1827 ms 14308 KB Output is correct
7 Correct 1650 ms 14228 KB Output is correct
8 Correct 1530 ms 14024 KB Output is correct
9 Correct 1270 ms 14352 KB Output is correct
10 Correct 1137 ms 14200 KB Output is correct
11 Correct 1314 ms 14620 KB Output is correct
12 Correct 1136 ms 14560 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2728 ms 17184 KB Output is correct
2 Correct 2492 ms 17356 KB Output is correct
3 Correct 2553 ms 17212 KB Output is correct
4 Correct 2645 ms 17424 KB Output is correct
5 Correct 2503 ms 17264 KB Output is correct
6 Correct 2663 ms 17520 KB Output is correct
7 Correct 2838 ms 17140 KB Output is correct
8 Correct 2986 ms 17428 KB Output is correct
9 Correct 207 ms 8164 KB Output is correct
10 Correct 1561 ms 17420 KB Output is correct
11 Correct 1555 ms 17408 KB Output is correct
12 Correct 1921 ms 17232 KB Output is correct
13 Correct 2075 ms 17768 KB Output is correct
14 Correct 1743 ms 14168 KB Output is correct
15 Correct 1146 ms 9972 KB Output is correct
16 Correct 1866 ms 14300 KB Output is correct
17 Correct 1657 ms 14148 KB Output is correct
18 Correct 213 ms 8164 KB Output is correct
19 Correct 1827 ms 14308 KB Output is correct
20 Correct 1650 ms 14228 KB Output is correct
21 Correct 1530 ms 14024 KB Output is correct
22 Correct 1270 ms 14352 KB Output is correct
23 Correct 1137 ms 14200 KB Output is correct
24 Correct 1314 ms 14620 KB Output is correct
25 Correct 1136 ms 14560 KB Output is correct
26 Correct 2643 ms 17216 KB Output is correct
27 Correct 2859 ms 17136 KB Output is correct
28 Correct 2762 ms 17384 KB Output is correct
29 Correct 2416 ms 17608 KB Output is correct
30 Correct 2886 ms 17556 KB Output is correct
31 Correct 2766 ms 17644 KB Output is correct
32 Correct 2885 ms 17392 KB Output is correct
33 Correct 2801 ms 17412 KB Output is correct
34 Correct 2812 ms 17376 KB Output is correct
35 Correct 2789 ms 17248 KB Output is correct
36 Correct 2493 ms 17672 KB Output is correct
37 Correct 2349 ms 17644 KB Output is correct
38 Correct 2349 ms 17648 KB Output is correct
39 Correct 1774 ms 17240 KB Output is correct
40 Correct 1670 ms 17480 KB Output is correct
41 Correct 1861 ms 17152 KB Output is correct
42 Correct 1860 ms 18132 KB Output is correct
43 Correct 1880 ms 17816 KB Output is correct
44 Correct 1765 ms 17928 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 71 ms 1528 KB Output is correct
4 Correct 26 ms 1408 KB Output is correct
5 Correct 94 ms 1400 KB Output is correct
6 Correct 81 ms 1400 KB Output is correct
7 Correct 86 ms 1272 KB Output is correct
8 Correct 94 ms 1400 KB Output is correct
9 Correct 87 ms 1272 KB Output is correct
10 Correct 97 ms 1400 KB Output is correct
11 Correct 95 ms 1400 KB Output is correct
12 Correct 104 ms 1400 KB Output is correct
13 Correct 100 ms 1528 KB Output is correct
14 Correct 95 ms 1400 KB Output is correct
15 Correct 98 ms 1404 KB Output is correct
16 Correct 97 ms 1272 KB Output is correct
17 Correct 89 ms 1272 KB Output is correct
18 Correct 2728 ms 17184 KB Output is correct
19 Correct 2492 ms 17356 KB Output is correct
20 Correct 2553 ms 17212 KB Output is correct
21 Correct 2645 ms 17424 KB Output is correct
22 Correct 2503 ms 17264 KB Output is correct
23 Correct 2663 ms 17520 KB Output is correct
24 Correct 2838 ms 17140 KB Output is correct
25 Correct 2986 ms 17428 KB Output is correct
26 Correct 207 ms 8164 KB Output is correct
27 Correct 1561 ms 17420 KB Output is correct
28 Correct 1555 ms 17408 KB Output is correct
29 Correct 1921 ms 17232 KB Output is correct
30 Correct 2075 ms 17768 KB Output is correct
31 Correct 1743 ms 14168 KB Output is correct
32 Correct 1146 ms 9972 KB Output is correct
33 Correct 1866 ms 14300 KB Output is correct
34 Correct 1657 ms 14148 KB Output is correct
35 Correct 213 ms 8164 KB Output is correct
36 Correct 1827 ms 14308 KB Output is correct
37 Correct 1650 ms 14228 KB Output is correct
38 Correct 1530 ms 14024 KB Output is correct
39 Correct 1270 ms 14352 KB Output is correct
40 Correct 1137 ms 14200 KB Output is correct
41 Correct 1314 ms 14620 KB Output is correct
42 Correct 1136 ms 14560 KB Output is correct
43 Execution timed out 3065 ms 24196 KB Time limit exceeded
44 Halted 0 ms 0 KB -