oj.uz

Submission #857523

# Submission time Handle Problem Language Result Execution time Memory
857523 2023-10-06T10:38:38 Z Abito Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 5972 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 i=0;i<c;i++) if (x[i]>y[i]) swap(x[i],y[i]);
    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) comp-=link(u.F,u.S);
        ans[k]=comp;
    }return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 471 ms 692 KB Output is correct
6 Correct 1144 ms 928 KB Output is correct
7 Correct 19 ms 604 KB Output is correct
8 Correct 18 ms 452 KB Output is correct
9 Correct 554 ms 784 KB Output is correct
10 Correct 838 ms 852 KB Output is correct
11 Correct 1236 ms 1108 KB Output is correct
12 Correct 1265 ms 1236 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2252 KB Output is correct
2 Correct 21 ms 2396 KB Output is correct
3 Execution timed out 15099 ms 5972 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2396 KB Output is correct
2 Correct 26 ms 2392 KB Output is correct
3 Correct 48 ms 2396 KB Output is correct
4 Correct 103 ms 2392 KB Output is correct
5 Correct 1897 ms 2428 KB Output is correct
6 Execution timed out 15022 ms 2740 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 471 ms 692 KB Output is correct
6 Correct 1144 ms 928 KB Output is correct
7 Correct 19 ms 604 KB Output is correct
8 Correct 18 ms 452 KB Output is correct
9 Correct 554 ms 784 KB Output is correct
10 Correct 838 ms 852 KB Output is correct
11 Correct 1236 ms 1108 KB Output is correct
12 Correct 1265 ms 1236 KB Output is correct
13 Correct 17 ms 2252 KB Output is correct
14 Correct 21 ms 2396 KB Output is correct
15 Execution timed out 15099 ms 5972 KB Time limit exceeded
16 Halted 0 ms 0 KB -