oj.uz

Submission #268714

# Submission time Handle Problem Language Result Execution time Memory
268714 2020-08-16T20:20:34 Z MKopchev Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 11776 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3200 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 1792 ms 3368 KB Output is correct
7 Correct 16 ms 2944 KB Output is correct
8 Correct 16 ms 2944 KB Output is correct
9 Correct 24 ms 3192 KB Output is correct
10 Correct 220 ms 3192 KB Output is correct
11 Correct 573 ms 3320 KB Output is correct
12 Correct 11055 ms 3612 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5876 KB Output is correct
2 Correct 37 ms 6264 KB Output is correct
3 Correct 121 ms 11512 KB Output is correct
4 Correct 55 ms 6400 KB Output is correct
5 Correct 296 ms 11776 KB Output is correct
6 Execution timed out 15029 ms 7376 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5868 KB Output is correct
2 Correct 38 ms 6012 KB Output is correct
3 Correct 43 ms 6272 KB Output is correct
4 Correct 58 ms 6400 KB Output is correct
5 Correct 1704 ms 6400 KB Output is correct
6 Execution timed out 15099 ms 6904 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3200 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 1792 ms 3368 KB Output is correct
7 Correct 16 ms 2944 KB Output is correct
8 Correct 16 ms 2944 KB Output is correct
9 Correct 24 ms 3192 KB Output is correct
10 Correct 220 ms 3192 KB Output is correct
11 Correct 573 ms 3320 KB Output is correct
12 Correct 11055 ms 3612 KB Output is correct
13 Correct 31 ms 5876 KB Output is correct
14 Correct 37 ms 6264 KB Output is correct
15 Correct 121 ms 11512 KB Output is correct
16 Correct 55 ms 6400 KB Output is correct
17 Correct 296 ms 11776 KB Output is correct
18 Execution timed out 15029 ms 7376 KB Time limit exceeded
19 Halted 0 ms 0 KB -