oj.uz

Submission #421914

# Submission time Handle Problem Language Result Execution time Memory
421914 2021-06-09T13:42:16 Z 반딧불(#7622) Collapse (JOI18_collapse) C++17
5 / 100
 488 ms 5952 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Query{
    int x, idx;
    Query(){}
    Query(int x, int idx): x(x), idx(idx){}
};

int n, k, q;
vector<Query> query[5002];
vector<int> link[5002];

int cut;
int ans[5002];
bool visited[5002];

void dfs(int x){
    visited[x] = 1;
    for(auto y: link[x]){
        if(visited[y]) continue;
        if((x <= cut) ^ (y <= cut)) continue;
        dfs(y);
    }
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
	n = N, k = (int)T.size(), q = (int)W.size();
	for(int i=0; i<q; i++){
        query[W[i]].push_back(Query(P[i], i));
	}
    for(int i=0; i<k; i++){
        if(T[i] == 0) link[X[i]].push_back(Y[i]), link[Y[i]].push_back(X[i]);
        else{
            link[X[i]].erase(find(link[X[i]].begin(), link[X[i]].end(), Y[i]));
            link[Y[i]].erase(find(link[Y[i]].begin(), link[Y[i]].end(), X[i]));
        }

        for(Query qr: query[i]){
            cut = qr.x;
            fill(visited, visited+n, 0);
            for(int i=0; i<n; i++){
                if(!visited[i]){
                    ans[qr.idx]++;
                    dfs(i);
                }
            }
        }
    }
    return vector<int> (ans, ans+q);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 82 ms 980 KB Output is correct
7 Correct 119 ms 744 KB Output is correct
8 Correct 117 ms 720 KB Output is correct
9 Correct 145 ms 1096 KB Output is correct
10 Correct 174 ms 972 KB Output is correct
11 Correct 488 ms 1172 KB Output is correct
12 Correct 375 ms 1220 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 5952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 5928 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 82 ms 980 KB Output is correct
7 Correct 119 ms 744 KB Output is correct
8 Correct 117 ms 720 KB Output is correct
9 Correct 145 ms 1096 KB Output is correct
10 Correct 174 ms 972 KB Output is correct
11 Correct 488 ms 1172 KB Output is correct
12 Correct 375 ms 1220 KB Output is correct
13 Runtime error 21 ms 5952 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -