oj.uz

Submission #857520

# Submission time Handle Problem Language Result Execution time Memory
857520 2023-10-06T10:33:51 Z Abito Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 3528 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#define ep insert
#define F first
#define S second
using namespace std;
const int N=5005;
int n,q,m,par[N],sz[N],c;
int getpar(int x){
    if (par[x]==x) return x;
    return par[x]=getpar(par[x]);
}
bool link(int x,int y){
    x=getpar(x);y=getpar(y);
    if (x==y) return 0;
    if (sz[x]>sz[y]) swap(x,y);
    sz[y]+=sz[x];
    par[x]=y;
    return 1;
}
std::vector<int> simulateCollapse(
	int NN,
	std::vector<int> t,
	std::vector<int> x,
	std::vector<int> y,
	std::vector<int> w,
	std::vector<int> p
) {
    n=NN;c=x.size();q=w.size();
    vector<int> ans(q);
    for (int k=0;k<q;k++){
        for (int i=0;i<n;i++) par[i]=i,sz[i]=1;
        int comp=n;
        set<pair<int,int>> s;
        for (int i=0;i<=w[k];i++){
            if (x[i]<=p[k] && y[i]>p[k]) continue;
            if (y[i]<=p[k] && x[i]>p[k]) continue;
            if (t[i]) s.erase({x[i],y[i]});
            else s.ep({x[i],y[i]});
        }
        for (auto u:s){
            int xx=u.F,yy=u.S;
            comp-=link(xx,yy);
        }
        ans[k]=comp;
    }return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2396 KB Output is correct
2 Incorrect 22 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2396 KB Output is correct
2 Correct 29 ms 2396 KB Output is correct
3 Correct 48 ms 2832 KB Output is correct
4 Correct 94 ms 2648 KB Output is correct
5 Correct 1940 ms 3164 KB Output is correct
6 Execution timed out 15011 ms 3528 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -