oj.uz

Submission #268728

# Submission time Handle Problem Language Result Execution time Memory
268728 2020-08-16T21:38:56 Z MKopchev Collapse (JOI18_collapse) C++14
100 / 100
 9334 ms 28532 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[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

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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5392 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 9 ms 5248 KB Output is correct
5 Correct 35 ms 5376 KB Output is correct
6 Correct 55 ms 5880 KB Output is correct
7 Correct 7 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 39 ms 5504 KB Output is correct
10 Correct 60 ms 5756 KB Output is correct
11 Correct 73 ms 6140 KB Output is correct
12 Correct 66 ms 6136 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 10080 KB Output is correct
2 Correct 70 ms 9020 KB Output is correct
3 Correct 2513 ms 13216 KB Output is correct
4 Correct 88 ms 9088 KB Output is correct
5 Correct 3501 ms 13176 KB Output is correct
6 Correct 664 ms 9592 KB Output is correct
7 Correct 5598 ms 24736 KB Output is correct
8 Correct 3585 ms 15068 KB Output is correct
9 Correct 62 ms 11628 KB Output is correct
10 Correct 79 ms 10020 KB Output is correct
11 Correct 381 ms 10364 KB Output is correct
12 Correct 3561 ms 16352 KB Output is correct
13 Correct 5891 ms 21600 KB Output is correct
14 Correct 7573 ms 28300 KB Output is correct
15 Correct 6660 ms 28532 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10100 KB Output is correct
2 Correct 65 ms 8764 KB Output is correct
3 Correct 96 ms 8740 KB Output is correct
4 Correct 106 ms 8680 KB Output is correct
5 Correct 261 ms 8320 KB Output is correct
6 Correct 669 ms 9080 KB Output is correct
7 Correct 4633 ms 18720 KB Output is correct
8 Correct 7138 ms 22596 KB Output is correct
9 Correct 71 ms 11244 KB Output is correct
10 Correct 346 ms 9572 KB Output is correct
11 Correct 8170 ms 25180 KB Output is correct
12 Correct 9334 ms 25400 KB Output is correct
13 Correct 8381 ms 25052 KB Output is correct
14 Correct 9275 ms 25436 KB Output is correct
15 Correct 8211 ms 25084 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5392 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 9 ms 5248 KB Output is correct
5 Correct 35 ms 5376 KB Output is correct
6 Correct 55 ms 5880 KB Output is correct
7 Correct 7 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 39 ms 5504 KB Output is correct
10 Correct 60 ms 5756 KB Output is correct
11 Correct 73 ms 6140 KB Output is correct
12 Correct 66 ms 6136 KB Output is correct
13 Correct 54 ms 10080 KB Output is correct
14 Correct 70 ms 9020 KB Output is correct
15 Correct 2513 ms 13216 KB Output is correct
16 Correct 88 ms 9088 KB Output is correct
17 Correct 3501 ms 13176 KB Output is correct
18 Correct 664 ms 9592 KB Output is correct
19 Correct 5598 ms 24736 KB Output is correct
20 Correct 3585 ms 15068 KB Output is correct
21 Correct 62 ms 11628 KB Output is correct
22 Correct 79 ms 10020 KB Output is correct
23 Correct 381 ms 10364 KB Output is correct
24 Correct 3561 ms 16352 KB Output is correct
25 Correct 5891 ms 21600 KB Output is correct
26 Correct 7573 ms 28300 KB Output is correct
27 Correct 6660 ms 28532 KB Output is correct
28 Correct 53 ms 10100 KB Output is correct
29 Correct 65 ms 8764 KB Output is correct
30 Correct 96 ms 8740 KB Output is correct
31 Correct 106 ms 8680 KB Output is correct
32 Correct 261 ms 8320 KB Output is correct
33 Correct 669 ms 9080 KB Output is correct
34 Correct 4633 ms 18720 KB Output is correct
35 Correct 7138 ms 22596 KB Output is correct
36 Correct 71 ms 11244 KB Output is correct
37 Correct 346 ms 9572 KB Output is correct
38 Correct 8170 ms 25180 KB Output is correct
39 Correct 9334 ms 25400 KB Output is correct
40 Correct 8381 ms 25052 KB Output is correct
41 Correct 9275 ms 25436 KB Output is correct
42 Correct 8211 ms 25084 KB Output is correct
43 Correct 3109 ms 13504 KB Output is correct
44 Correct 5836 ms 23672 KB Output is correct
45 Correct 3604 ms 14072 KB Output is correct
46 Correct 6669 ms 24312 KB Output is correct
47 Correct 72 ms 11628 KB Output is correct
48 Correct 99 ms 10112 KB Output is correct
49 Correct 467 ms 10492 KB Output is correct
50 Correct 1577 ms 11908 KB Output is correct
51 Correct 4088 ms 15224 KB Output is correct
52 Correct 6145 ms 19000 KB Output is correct
53 Correct 6037 ms 18544 KB Output is correct
54 Correct 7217 ms 21196 KB Output is correct
55 Correct 6584 ms 20808 KB Output is correct
56 Correct 7091 ms 22904 KB Output is correct
57 Correct 8173 ms 25108 KB Output is correct
58 Correct 8877 ms 25540 KB Output is correct
59 Correct 8180 ms 27256 KB Output is correct
60 Correct 9325 ms 27552 KB Output is correct