oj.uz

Submission #603535

# Submission time Handle Problem Language Result Execution time Memory
603535 2022-07-24T07:53:08 Z 조영욱(#8429) Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 255728 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

int sp;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
int n,c,q;
const int sz=131072;
vector<P> query[sz];
vector<int> ret;
int p[100000];
vector<P> seg[sz*2];
stack<P> st;

int find(int a) {
    return p[a]<0?a:find(p[a]);
}

bool merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return false;
    }
    if (-p[a]<=-p[b]) {
        swap(a,b);
    }
    if (p[a]==p[b]) {
        st.push(P(a,p[a]));
        p[a]=p[a]-1;
    }
    st.push(P(b,p[b]));
    p[b]=a;
    return true;
}

set<P> s;

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> pp
) {
    //st.push(P(-1,-1));
    sp=pp[0];
    n=N;
    c=T.size();
    q=pp.size();
    ret.resize(q);
    for(int i=0;i<q;i++) {
        query[W[i]].push_back(P(pp[i],i));
    }
    for(int i=0;i<c;i++) {
        if (X[i]>Y[i]) {
            swap(X[i],Y[i]);
        }
        if (T[i]==0) {
            s.insert(P(X[i],Y[i]));
        }
        else {
            s.erase(P(X[i],Y[i]));
        }
        for(int j=0;j<query[i].size();j++) {
            memset(p,-1,sizeof(p));
            for(auto now:s) {
                if (now.first>query[i][j].first||now.second<=query[i][j].first) {
                    merge(now.first,now.second);
                }
            }
            int val=0;
            for(int k=0;k<n;k++) {
                if (p[k]<0) {
                    val++;
                }
            }
            ret[query[i][j].second]=val;
        }
    }
	return ret;
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10288 KB Output is correct
2 Correct 50 ms 10104 KB Output is correct
3 Correct 51 ms 10240 KB Output is correct
4 Correct 52 ms 10432 KB Output is correct
5 Correct 56 ms 10528 KB Output is correct
6 Correct 331 ms 14688 KB Output is correct
7 Correct 62 ms 10160 KB Output is correct
8 Correct 64 ms 10312 KB Output is correct
9 Correct 65 ms 11328 KB Output is correct
10 Correct 136 ms 25556 KB Output is correct
11 Correct 772 ms 111580 KB Output is correct
12 Correct 712 ms 80952 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1244 ms 13044 KB Output is correct
2 Correct 1054 ms 14240 KB Output is correct
3 Correct 1064 ms 24620 KB Output is correct
4 Correct 1088 ms 20876 KB Output is correct
5 Correct 1581 ms 78244 KB Output is correct
6 Correct 6547 ms 96312 KB Output is correct
7 Execution timed out 15096 ms 224204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 13052 KB Output is correct
2 Correct 903 ms 15052 KB Output is correct
3 Correct 931 ms 19548 KB Output is correct
4 Correct 943 ms 21252 KB Output is correct
5 Correct 1473 ms 90956 KB Output is correct
6 Correct 6363 ms 96676 KB Output is correct
7 Execution timed out 15092 ms 255728 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10288 KB Output is correct
2 Correct 50 ms 10104 KB Output is correct
3 Correct 51 ms 10240 KB Output is correct
4 Correct 52 ms 10432 KB Output is correct
5 Correct 56 ms 10528 KB Output is correct
6 Correct 331 ms 14688 KB Output is correct
7 Correct 62 ms 10160 KB Output is correct
8 Correct 64 ms 10312 KB Output is correct
9 Correct 65 ms 11328 KB Output is correct
10 Correct 136 ms 25556 KB Output is correct
11 Correct 772 ms 111580 KB Output is correct
12 Correct 712 ms 80952 KB Output is correct
13 Correct 1244 ms 13044 KB Output is correct
14 Correct 1054 ms 14240 KB Output is correct
15 Correct 1064 ms 24620 KB Output is correct
16 Correct 1088 ms 20876 KB Output is correct
17 Correct 1581 ms 78244 KB Output is correct
18 Correct 6547 ms 96312 KB Output is correct
19 Execution timed out 15096 ms 224204 KB Time limit exceeded
20 Halted 0 ms 0 KB -