제출 #233278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233278		VEGAnn	Tenis (COI19_tenis)	C++14	51 / 100	1079 ms	22260 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];
int mn[3], men[3], lst[3];
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));

    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;

    if (q < 11){
        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;
        }

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

            if (tp == 1){
                int x; cin >> x; x--;

                fill(mrk, mrk + n, 0);

                mn[0] = mn[1] = mn[2] = n;

                for (int tp = 0; tp < 3; tp++)
                    lst[tp] = loc[tp][x];

                for (int tp = 0; tp < 3; tp++)
                for (int i = loc[tp][x]; i < n; i++) {
                    mrk[a[tp][i]] = 1;

                    for (int j = 0; j < 3; j++)
                        mn[j] = min(mn[j], loc[j][a[tp][i]]);
                }

                bool was = 1;

                while (was) {
                    was = 0;

                    men[0] = mn[0];
                    men[1] = mn[1];
                    men[2] = mn[2];

                    for (int tp = 0; tp < 3; tp++)
                    for (int i = mn[tp]; i < lst[tp]; i++)
                        if (!mrk[a[tp][i]]){
                            for (int j = 0; j < 3; j++)
                                men[j] = min(men[j], loc[j][a[tp][i]]);
                            was = 1;
                            mrk[a[tp][i]] = 1;
                        }

                    lst[0] = mn[0];
                    lst[1] = mn[1];
                    lst[2] = mn[2];

                    mn[0] = men[0];
                    mn[1] = men[1];
                    mn[2] = men[2];
                }

                bool ok = 1;

                for (int i = 0; i < n && ok; i++)
                    if (!mrk[i])
                        ok = 0;

                cout << (ok ? "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]]);
            }
        }

        return 0;
    }

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