Submission #625971

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625971	2022-08-11T05:17:45 Z	teee	Collapse (JOI18_collapse)	C++14	Compilation error	0 ms	0 KB

collapse

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <queue>
#include <set>
#include <map>
#define all(x)x.begin(),x.end()
#define pack(x)sort(all(x));x.erase(unique(all(x)),x.end())
#define gi(x,v)lower_bound(all(x),v)-x.begin()
using namespace std;
using ll=long long;
using ld=long double;
vector<int> pre[100'010],suf[100'010];
const int sq=316;
struct ed{
    int t,a,b;
};
ed v[100'010];
struct que{
    int w,p,idx;
};
vector<que> qq[100'000];
vector<que> qqs[10'000];
int ans[100'010];
int par[100'010];
int sz[100'010];
int remPnt[100'010];
int find(int a){
    return par[a]?find(par[a]):a;
}vector<array<int,2>> st;
int Mcnt;
void merge(int a,int b){
    a=find(a);b=find(b);
    if(a==b)return;
    if(sz[a]>sz[b])swap(a,b);
    par[a]=b;
    sz[b]+=sz[a];Mcnt++;
    st.push_back({a,b});
}map<pair<int,int>,int> mp;
vector<int> now,nxt,chk;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,c,q,t,a,b;
    cin>>n>>c>>q;
    for(int i=0;i<c;i++){
        cin>>t>>a>>b;a++;b++;
        if(a>b)swap(a,b);
        v[i]={t,a,b};
        if(t==0)mp[{a,b}]=i;
        else remPnt[mp[{a,b}]]=i;
        remPnt[i]=c+1;
    }mp.clear();
    for(int i=0;i<q;i++){
        cin>>a>>b;b++;
        qqs[a/sq].push_back({a,b,i});
        ans[i]=n;
    }for(int i=0,s=0,e=sq-1;s<c;i++,s+=sq,e=min(e+sq,c-1)){
        Mcnt=0;
        for(int j=1;j<=n;j++){
            par[j]=0;sz[j]=1;
            pre[j].clear();
            qq[j].clear();
            suf[j].clear();
        }nxt.clear();chk.clear();
        for(auto j:qqs[i]){
            qq[j.p].push_back(j);
        }
        for(auto j:now){
            if(remPnt[j]<=e)chk.push_back(j);
            else {
                nxt.push_back(j);
                pre[v[j].b].push_back(v[j].a);
                suf[v[j].a].push_back(v[j].b);
            }
        }swap(nxt,now);
        for(int j=s;j<=e;j++){
            if(v[j].t==1)continue;
            chk.push_back(j);
        }
        for(int j=1;j<=n;j++){
            for(auto k:pre[j])merge(k,j);
            st.clear();
            for(auto k:qq[j]){
                for(auto x:chk){
                    if(x<=k.w&&k.w<remPnt[x]&&v[x].b<=j)merge(v[x].a,v[x].b);
                }ans[k.idx]-=Mcnt;
                while(!st.empty()){
                    a=st.back()[0];
                    b=st.back()[1];
                    par[a]=0;
                    sz[b]-=sz[a];
                    Mcnt--;
                    st.pop_back();
                }
            }
        }

        Mcnt=0;
        for(int j=1;j<=n;j++){
            par[j]=0;sz[j]=1;
        }

        for(int j=n;j>=2;j--){
            for(auto k:suf[j])merge(k,j);
            st.clear();
            for(auto k:qq[j-1]){
                for(auto x:chk){
                    if(x<=k.w&&k.w<remPnt[x]&&j<=v[x].a)merge(v[x].a,v[x].b);
                }ans[k.idx]-=Mcnt;
                while(!st.empty()){
                    a=st.back()[0];
                    b=st.back()[1];
                    par[a]=0;
                    sz[b]-=sz[a];
                    Mcnt--;
                    st.pop_back();
                }
            }
        }

        for(auto x:chk){
            if(e<remPnt[x])now.push_back(x);
        }
    }for(int i=0;i<q;i++){
        cout<<ans[i]<<'\n';
    }
}

Compilation message

/usr/bin/ld: /tmp/ccimuQOd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYN55Fh.o:collapse.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccimuQOd.o: in function `main':
grader.cpp:(.text.startup+0x227): undefined reference to `simulateCollapse(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status