oj.uz

Submission #375325

# Submission time Handle Problem Language Result Execution time Memory
375325 2021-03-09T08:46:14 Z rrrr10000 Collapse (JOI18_collapse) C++14
30 / 100
 5244 ms 15796 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define dame(a) {out(a);return 0;}
#define rsort(a) {sort(all(a));reverse(all(a));}
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 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> void outp(T p){printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvp(T v){for(auto p:v)printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
#include "collapse.h"
class UF{
    vi par,sz;
public:
    ll cnt;
    vp memo;
    UF(ll n){
        par=vi(n,-1);sz=vi(n,1);cnt=n;
    }
    ll root(ll i){if(par[i]==-1)return i;return root(par[i]);}
    void merge(ll a,ll b,bool flag){
        a=root(a);b=root(b);
        if(a==b)return;
        if(sz[a]>sz[b])swap(a,b);
        if(flag){memo.pb(a,par[a]);memo.pb(b,sz[b]);}
        par[a]=b;sz[b]+=sz[a];cnt--;
    }
    void rollback(){
        while(!memo.empty()){
            sz[memo.back().fi]=memo.back().se;memo.pop_back();
            par[memo.back().fi]=memo.back().se;memo.pop_back();
            cnt++;
        }
    }
};
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
    int C=T.size(),Q=W.size(),B=300;
    rep(i,C)if(X[i]>Y[i])swap(X[i],Y[i]);
	vvp query(C/B+1);
    rep(i,Q){
        query[W[i]/B].pb(P[i],i);
    }
    vector<int> ans(Q);
    rep(i,query.size())sort(all(query[i]));
    rep(i,query.size()){
        UF uf(n);
        vp s;
        rep(j,i*B)s.pb(Y[j],X[j]);
        sort(all(s));
        ll w=0;
        for(auto x:query[i]){
            while(w!=s.size()&&s[w].fi<=x.fi){
                uf.merge(s[w].fi,s[w].se,0);
                w++;
            }
            REP(j,i*B,W[x.se]+1)if(Y[j]<=x.fi)uf.merge(X[j],Y[j],1);
            ans[x.se]+=uf.cnt-(n-P[x.se]-1);
            uf.rollback();
        }
    }
    // outv(ans);
    rep(i,query.size())reverse(all(query[i]));
    rep(i,query.size()){
        UF uf(n);
        vp s;
        rep(j,i*B)s.pb(X[j],Y[j]);
        rsort(s);
        ll w=0;
        for(auto x:query[i]){
            while(w!=s.size()&&s[w].fi>x.fi){
                uf.merge(s[w].fi,s[w].se,0);
                w++;
            }
            REP(j,i*B,W[x.se]+1)if(X[j]>x.fi)uf.merge(X[j],Y[j],1);
            ans[x.se]+=uf.cnt-P[x.se]-1;
            uf.rollback();
        }
    }
    return ans;
}

Compilation message

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:69:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             while(w!=s.size()&&s[w].fi<=x.fi){
      |                   ~^~~~~~~~~~
collapse.cpp:87:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             while(w!=s.size()&&s[w].fi>x.fi){
      |                   ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1008 KB Output is correct
2 Incorrect 3 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4448 KB Output is correct
2 Incorrect 44 ms 4448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4452 KB Output is correct
2 Correct 49 ms 4448 KB Output is correct
3 Correct 62 ms 4448 KB Output is correct
4 Correct 71 ms 4576 KB Output is correct
5 Correct 223 ms 4492 KB Output is correct
6 Correct 158 ms 5356 KB Output is correct
7 Correct 2621 ms 11496 KB Output is correct
8 Correct 4792 ms 14036 KB Output is correct
9 Correct 49 ms 6236 KB Output is correct
10 Correct 398 ms 6716 KB Output is correct
11 Correct 4981 ms 15720 KB Output is correct
12 Correct 5244 ms 15796 KB Output is correct
13 Correct 5142 ms 15632 KB Output is correct
14 Correct 5220 ms 15528 KB Output is correct
15 Correct 5017 ms 15768 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1008 KB Output is correct
2 Incorrect 3 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -