oj.uz

Submission #603357

# Submission time Handle Problem Language Result Execution time Memory
603357 2022-07-24T04:49:41 Z 반딧불(#8427) Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 9920 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, q;
int ex[100002], ey[100002], et[100002];
int qx[100002], qt[100002];
vector<int> link[100002];
bool visited[100002];
int ans[100002];

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

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
    n = N, m = (int)T.size(), q = (int)W.size();
    for(int i=1; i<=m; i++){
        ex[i] = X[i-1];
        ey[i] = Y[i-1];
        et[i] = T[i-1];
        ex[i]++, ey[i]++;
        if(ex[i] > ey[i]) swap(ex[i], ey[i]);
    }
    for(int i=1; i<=q; i++){
        qx[i] = P[i-1]+1;
        qt[i] = W[i-1]+1;
    }

    for(int i=1; i<=q; i++){
        set<pair<int, int> > st;
        for(int x=1; x<=qt[i]; x++){
            if(et[x]) st.erase(make_pair(ex[x], ey[x]));
            else st.insert(make_pair(ex[x], ey[x]));
        }
        for(int i=1; i<=n; i++) link[i].clear(), visited[i] = 0;
        for(auto p: st){
            if(p.first <= qx[i] && qx[i] < p.second) continue;
            link[p.first].push_back(p.second);
            link[p.second].push_back(p.first);
        }
        for(int x=1; x<=n; x++){
            if(!visited[x]) dfs(x), ans[i]++;
        }
    }
    return vector<int> (ans+1, ans+q+1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3040 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 8 ms 2840 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 853 ms 3044 KB Output is correct
6 Correct 2229 ms 3452 KB Output is correct
7 Correct 81 ms 2772 KB Output is correct
8 Correct 85 ms 2836 KB Output is correct
9 Correct 906 ms 3392 KB Output is correct
10 Correct 1547 ms 3328 KB Output is correct
11 Correct 2544 ms 3716 KB Output is correct
12 Correct 2500 ms 3568 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6096 KB Output is correct
2 Correct 36 ms 6100 KB Output is correct
3 Execution timed out 15052 ms 9920 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6144 KB Output is correct
2 Correct 47 ms 6092 KB Output is correct
3 Correct 85 ms 6232 KB Output is correct
4 Correct 179 ms 6304 KB Output is correct
5 Correct 2825 ms 6468 KB Output is correct
6 Execution timed out 15019 ms 6484 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3040 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 8 ms 2840 KB Output is correct
4 Correct 11 ms 2772 KB Output is correct
5 Correct 853 ms 3044 KB Output is correct
6 Correct 2229 ms 3452 KB Output is correct
7 Correct 81 ms 2772 KB Output is correct
8 Correct 85 ms 2836 KB Output is correct
9 Correct 906 ms 3392 KB Output is correct
10 Correct 1547 ms 3328 KB Output is correct
11 Correct 2544 ms 3716 KB Output is correct
12 Correct 2500 ms 3568 KB Output is correct
13 Correct 26 ms 6096 KB Output is correct
14 Correct 36 ms 6100 KB Output is correct
15 Execution timed out 15052 ms 9920 KB Time limit exceeded
16 Halted 0 ms 0 KB -