Submission #1032532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032532		vjudge1	Collapse (JOI18_collapse)	C++17	0 / 100	24 ms	15964 KiB

collapse

#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
struct dsurol{
    int par[100100],dep[100100],ans;
    stack<pair<int,int>>stk;
    dsurol(){memset(par,0,sizeof par);memset(dep,0,sizeof dep);ans=0;}
    void init(int n){
        ans=n;
    }
    int abp(int n){
        return par[n]?abp(par[n]):n;
    }
    void merge(int a,int b){
        a=abp(++a);
        b=abp(++b);
        if(a-b){
            ans--;
            if(dep[a]<dep[b])
                swap(a,b);
            par[b]=a;
            stk.push({b,dep[a]});
            dep[a]=max(dep[a],dep[b]+1);
        }
    }
    void rerol(){
        auto[b,prvd]=stk.top();
        stk.pop();
        dep[par[b]]=prvd;
        par[b]=0;
        ans++;
    }
    void rolbak(int n){
        while(stk.size()>n)
            rerol();
    }
} dsu;
vector<pair<int,int>>whattoad[1<<19];
void add(int i,int l,int r,int ll,int rr,pair<int,int>K){
    if(ll<=l&&r<=rr)
        return whattoad[i].push_back(K);
    if(ll>r||l>rr) return;
    add(i*2,l,l+r>>1,ll,rr,K);
    add(i*2+1,l+r+2>>1,r,ll,rr,K);
}
vector<int>ans;
void solve(int i,int l,int r){
    int k=dsu.stk.size();
    for(auto&[a,b]:whattoad[i])
        dsu.merge(a,b);
    if(l==r)
        ans.push_back(dsu.ans);
    else solve(i*2,l,l+r>>1),
        solve(i*2+1,l+r+2>>1,r);
    dsu.rolbak(k);
}
set<int>adj[5000],adj2[5000];
bitset<5000>vis;
map<pair<int,int>,int> mp;
void dfs(int n){
    if(vis[n])return;
    vis[n]=1;
    for(auto i:adj2[n])  
        dfs(i);
}
int calc(int N){
    int ans=0;
    for(int i=0;i<N;i++)
        if(!vis[i])
            dfs(i),ans++;
    vis.reset();
    return ans;
}
void setedg(int nod,int N){
    for(int i=0;i<N;i++)
        adj2[i]=adj[i];
    for(int i=0;i<=nod;i++) {
        while(adj2[i].size()) {
            int k=*--adj2[i].end();
            if(k<=nod)break;
            adj2[i].erase(k);
            adj2[k].erase(i);
        }
    }
}
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P) {
    dsu.init(N);
    int K=T.size();
    vector<int>v=W;
    for(int i=0;i<K;i++){
        int t=T[i];
        if(t){
            adj[X[i]].insert(Y[i]);
            adj[Y[i]].insert(X[i]);
        } else {
            adj[X[i]].erase(Y[i]);
            adj[Y[i]].erase(X[i]);
        }
        for(int h=0;h<W.size();h++){
            if(W[h]==i+1)
                setedg(P[h],N),v[h]=calc(N);
        }
    }
    return v;
}

Compilation message (stderr)

collapse.cpp: In member function 'void dsurol::rolbak(int)':
collapse.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         while(stk.size()>n)
      |               ~~~~~~~~~~^~
collapse.cpp: In function 'void add(int, int, int, int, int, std::pair<int, int>)':
collapse.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     add(i*2,l,l+r>>1,ll,rr,K);
      |               ~^~
collapse.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     add(i*2+1,l+r+2>>1,r,ll,rr,K);
      |               ~~~^~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:53:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     else solve(i*2,l,l+r>>1),
      |                      ~^~
collapse.cpp:54:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         solve(i*2+1,l+r+2>>1,r);
      |                     ~~~^~
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:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int h=0;h<W.size();h++){
      |                     ~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35