oj.uz

답안 #268727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268727 2020-08-16T21:37:00 Z MKopchev Collapse (JOI18_collapse) C++14
30 / 100
 9207 ms 27668 KB 
#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[i],Y[i]}))
            {
                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

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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 5504 KB Output is correct
2 Correct 9 ms 5248 KB Output is correct
3 Incorrect 8 ms 5248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 10476 KB Output is correct
2 Incorrect 71 ms 9396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 10476 KB Output is correct
2 Correct 81 ms 9144 KB Output is correct
3 Correct 92 ms 9192 KB Output is correct
4 Correct 139 ms 9064 KB Output is correct
5 Correct 219 ms 8704 KB Output is correct
6 Correct 678 ms 9464 KB Output is correct
7 Correct 4860 ms 20252 KB Output is correct
8 Correct 7215 ms 24292 KB Output is correct
9 Correct 71 ms 11756 KB Output is correct
10 Correct 324 ms 9984 KB Output is correct
11 Correct 7925 ms 27296 KB Output is correct
12 Correct 9190 ms 27476 KB Output is correct
13 Correct 8257 ms 27224 KB Output is correct
14 Correct 9207 ms 27668 KB Output is correct
15 Correct 8266 ms 27268 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 5504 KB Output is correct
2 Correct 9 ms 5248 KB Output is correct
3 Incorrect 8 ms 5248 KB Output isn't correct
4 Halted 0 ms 0 KB -