Submission #233274

#	Time	Username	Problem	Language	Result	Execution time	Memory
233274		VEGAnn	Tenis (COI19_tenis)	C++14	21 / 100	165 ms	23280 KiB

tenis

#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 != 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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 49