Submission #268714

#	Time	Username	Problem	Language	Result	Execution time	Memory
268714		MKopchev	Collapse (JOI18_collapse)	C++14	5 / 100	15099 ms	11776 KiB

collapse

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

const int nmax=1e5+42;

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

set< pair<int,int> > edges;

int parent[nmax];

int components;

int root(int node)
{
    while(parent[node]!=node)node=parent[node];
    return node;
}
void my_merge(int u,int v)
{
    u=root(u);
    v=root(v);

    if(u==v)return;

    components--;

    parent[u]=v;
}
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)
{
	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);

	for(int i=0;i<T.size();i++)
	{
	    if(T[i]==0)edges.insert({X[i],Y[i]});
	    else edges.erase({X[i],Y[i]});
        /*
	    cout<<i<<" : "<<endl;
	    for(auto k:edges)cout<<k.first<<" "<<k.second<<endl;
        */
	    for(auto k:seen[i])
        {
            components=N;
            for(int j=0;j<N;j++)parent[j]=j;

            for(auto p:edges)
                if((p.first<=k.first&&p.second<=k.first)||(p.first>k.first&&p.second>k.first))my_merge(p.first,p.second);

            //cout<<k.first<<" -> "<<components<<endl;

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

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