Submission #268728

#	Time	Username	Problem	Language	Result	Execution time	Memory
268728		MKopchev	Collapse (JOI18_collapse)	C++14	100 / 100	9334 ms	28532 KiB

collapse

#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

int n;

vector< pair<int/*cut*/,int/*id*/> >seen[nmax];

set< pair<int,int> > edges;

int parent[nmax],sz[nmax];

int root(int node)
{
    while(parent[node]!=node)node=parent[node];
    return node;
}

pair<int/*big*/,int/*small*/> mem[nmax];
int pointer=0;

void my_merge(int u,int v)
{
    /*
    cout<<"my_merge "<<u<<" "<<v<<endl;
    for(int i=0;i<n;i++)cout<<root(i)<<" ";cout<<endl;
    */

    u=root(u);
    v=root(v);

    if(u==v)return;

    if(sz[u]<sz[v])swap(u,v);

    mem[pointer]={u,v};
    pointer++;

    parent[v]=u;
    sz[u]+=sz[v];
}

vector<int> other_edge[nmax];


void init()
{
    for(int i=0;i<n;i++)
    {
        sz[i]=1;
        parent[i]=i;
        other_edge[i]={};
    }
    pointer=0;
}

set<pair<int,int> > forced,cut;

struct info
{
    int cut_line,when,id;
};
vector<info> active={};
bool cmp(info a,info b)
{
    return a.cut_line<b.cut_line;
}

bool cmp_2(info a,info b)
{
    return a.cut_line>b.cut_line;
}

void pop_pointer(int to)
{
    while(pointer>to)
    {
        pointer--;
        sz[mem[pointer].first]-=sz[mem[pointer].second];
        parent[mem[pointer].second]=mem[pointer].second;
    }
}
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)
{
    n=N;

	for(int i=0;i<W.size();i++)
        seen[W[i]].push_back({P[i],i});

	int C=T.size();

	for(int i=0;i<C;i++)
        if(X[i]>Y[i])swap(X[i],Y[i]);

	vector<int> outp(W.size(),N);

	int BLOCK_SIZE=sqrt(C)+1;

	for(int i=0;i<C;i+=BLOCK_SIZE)
	{
	    init();

	    int STOP=T.size()-1;
	    STOP=min(STOP,i+BLOCK_SIZE-1);

	    forced=edges;
        cut={};

	    for(int j=i;j<=STOP;j++)
            if(T[j]==1&&forced.count({X[j],Y[j]}))
            {
                forced.erase({X[j],Y[j]});
                cut.insert({X[j],Y[j]});
            }
        /*
        cout<<"forced: "<<endl;
        for(auto k:forced)cout<<k.first<<" "<<k.second<<endl;
        cout<<"---"<<endl;
        */
        active={};
        for(int t=i;t<=STOP;t++)
            for(auto k:seen[t])
            {
                info cur;
                cur.cut_line=k.first;
                cur.id=k.second;
                cur.when=t;
                active.push_back(cur);
            }
        sort(active.begin(),active.end(),cmp);

        for(auto k:forced)
            other_edge[k.second].push_back(k.first);

        int j=-1;

        for(auto k:active)
        {
            while(j<k.cut_line)
            {
                j++;
                for(auto p:other_edge[j])
                    my_merge(p,j);
            }

            set< pair<int,int> > cur_cut=cut;

            for(int j=i;j<=k.when;j++)
                if(T[j]==0)cur_cut.insert({X[j],Y[j]});
                else cur_cut.erase({X[j],Y[j]});
            /*
            cout<<k.cut_line<<" "<<k.when<<" "<<k.id<<" j= "<<j<<endl;
            cout<<"cur_cut: "<<endl;
            for(auto p:cur_cut)cout<<p.first<<" "<<p.second<<endl;
            */
            int mem_pointer=pointer;

            for(auto p:cur_cut)
                if(p.first<=k.cut_line&&p.second<=k.cut_line)
                    my_merge(p.first,p.second);
            /*
            cout<<"pointer= "<<pointer<<endl;
            cout<<"---"<<endl;
            */
            outp[k.id]-=pointer;

            pop_pointer(mem_pointer);
        }
        /*
	    cout<<i<<" : "<<endl;
	    for(auto k:edges)cout<<k.first<<" "<<k.second<<endl;
        */

        init();
        sort(active.begin(),active.end(),cmp_2);

        for(auto k:forced)
            other_edge[k.first].push_back(k.second);

        //cout<<"---\n---\n---\n"<<endl;

        j=n;

        for(auto k:active)
        {
            while(j-1>k.cut_line)
            {
                j--;
                for(auto p:other_edge[j])
                    my_merge(p,j);
            }

            set< pair<int,int> > cur_cut=cut;

            for(int j=i;j<=k.when;j++)
                if(T[j]==0)cur_cut.insert({X[j],Y[j]});
                else cur_cut.erase({X[j],Y[j]});
            /*
            cout<<k.cut_line<<" "<<k.when<<" "<<k.id<<" j= "<<j<<endl;
            cout<<"cur_cut: "<<endl;
            for(auto p:cur_cut)cout<<p.first<<" "<<p.second<<endl;
            */
            int mem_pointer=pointer;

            for(auto p:cur_cut)
                if(p.first>k.cut_line&&p.second>k.cut_line)
                    my_merge(p.first,p.second);
            /*
            cout<<"pointer= "<<pointer<<endl;
            cout<<"---"<<endl;
            */

            outp[k.id]-=pointer;

            pop_pointer(mem_pointer);
        }

        for(int j=i;j<=STOP;j++)
            if(T[j]==0)edges.insert({X[j],Y[j]});
            else edges.erase({X[j],Y[j]});
	}
	return outp;
}
/*
int main()
{
	int N, C, Q;
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	for(auto i : res) {
		printf("%d\n", i);
	}
}
*/

Compilation message (stderr)

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:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int i=0;i<W.size();i++)
      |              ~^~~~~~~~~

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