oj.uz

Submission #233273

# Submission time Handle Problem Language Result Execution time Memory
233273 2020-05-20T08:18:53 Z VEGAnn Tenis (COI19_tenis) C++14
0 / 100
 143 ms 19604 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;
    }

    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 != 0) 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 19604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -