oj.uz

Submission #233276

# Submission time Handle Problem Language Result Execution time Memory
233276 2020-05-20T08:21:13 Z VEGAnn Tenis (COI19_tenis) C++14
39 / 100
 500 ms 22136 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 100100;
const int md = int(1e9) + 7;
vector<int> g[N], ts, gr[N], co[N];
int loc[3][N], n, q, a[3][N], kol, comp[N], in[N];
bool mrk[N];

void top_sort(int v){
    if (mrk[v]) return;

    mrk[v] = 1;

    for (int u : g[v])
        top_sort(u);

    ts.PB(v);
}

void dfs(int v){
    if (comp[v] >= 0) return;

    comp[v] = kol;

    for (int u : gr[v])
        dfs(u);
}

void build(){
    for (int i = 0; i < n; i++) {
        g[i].clear();
        gr[i].clear();
        comp[i] = -1;
        in[i] = 0;
    }

    for (int tp = 0; tp < 3; tp++)
    for (int i = 1; i < n; i++) {
        g[a[tp][i - 1]].PB(a[tp][i]);
        gr[a[tp][i]].PB(a[tp][i - 1]);
    }

    fill(mrk, mrk + n, 0);
    ts.clear();

    for (int i = 0; i < n; i++){
        if (mrk[i]) continue;

        top_sort(i);
    }

    reverse(all(ts));

    fill(mrk, mrk + n, 0);

    kol = 0;

    for (int v : ts){
        if (comp[v] >= 0) continue;

        dfs(v);
        kol++;
    }

    for (int tp = 0; tp < 3; tp++)
    for (int i = 1; i < n; i++) {
        int cur = comp[a[tp][i]];

        if (comp[a[tp][i - 1]] == cur) continue;

        if (in[cur] == 0)
            kol--;
        in[cur]++;
    }

    fill(mrk, mrk + n, 0);

    if (kol != 1) return;

    int cur = -1;

    for (int i = 0; ; i++)
        if (in[i] == 0){
            cur = i;
            break;
        }

    assert(cur != -1);

    for (int i = 0; i < n; i++)
        if (comp[i] == cur)
            mrk[i] = 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    for (int tp = 0; tp < 3; tp++)
    for (int i = 0; i < n; i++){
        int x; cin >> x;
        x--;

        loc[tp][x] = i;
        a[tp][i] = x;
    }

    build();

    for (; q; q--){
        int tp; cin >> tp;

        if (tp == 1){
            int x; cin >> x; x--;
            cout << (mrk[x] ? "DA\n" : "NE\n");
        } else {
            int x, y; cin >> tp >> x >> y;
            tp--; x--; y--;

            swap(loc[tp][x], loc[tp][y]);
            swap(a[tp][loc[tp][x]], a[tp][loc[tp][y]]);

            build();
        }
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 10 ms 7552 KB Output is correct
10 Correct 10 ms 7552 KB Output is correct
11 Correct 10 ms 7552 KB Output is correct
12 Correct 10 ms 7552 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 10 ms 7552 KB Output is correct
10 Correct 10 ms 7552 KB Output is correct
11 Correct 10 ms 7552 KB Output is correct
12 Correct 10 ms 7552 KB Output is correct
13 Correct 438 ms 22136 KB Output is correct
14 Correct 462 ms 20852 KB Output is correct
15 Correct 373 ms 21368 KB Output is correct
16 Correct 304 ms 19828 KB Output is correct
17 Correct 135 ms 20088 KB Output is correct
18 Correct 296 ms 20228 KB Output is correct
19 Correct 245 ms 20088 KB Output is correct
20 Execution timed out 657 ms 19896 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 18928 KB Output is correct
2 Correct 155 ms 20336 KB Output is correct
3 Correct 143 ms 20336 KB Output is correct
4 Correct 134 ms 21232 KB Output is correct
5 Correct 143 ms 19316 KB Output is correct
6 Correct 130 ms 20212 KB Output is correct
7 Correct 153 ms 19184 KB Output is correct
8 Correct 143 ms 20592 KB Output is correct
9 Correct 169 ms 20336 KB Output is correct
10 Correct 143 ms 20084 KB Output is correct
11 Correct 138 ms 19316 KB Output is correct
12 Correct 133 ms 20724 KB Output is correct
13 Correct 141 ms 20384 KB Output is correct
14 Correct 156 ms 20728 KB Output is correct
15 Correct 143 ms 21236 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 10 ms 7552 KB Output is correct
10 Correct 10 ms 7552 KB Output is correct
11 Correct 10 ms 7552 KB Output is correct
12 Correct 10 ms 7552 KB Output is correct
13 Correct 438 ms 22136 KB Output is correct
14 Correct 462 ms 20852 KB Output is correct
15 Correct 373 ms 21368 KB Output is correct
16 Correct 304 ms 19828 KB Output is correct
17 Correct 135 ms 20088 KB Output is correct
18 Correct 296 ms 20228 KB Output is correct
19 Correct 245 ms 20088 KB Output is correct
20 Execution timed out 657 ms 19896 KB Time limit exceeded
21 Halted 0 ms 0 KB -