Submission #233395

#	Time	Username	Problem	Language	Result	Execution time	Memory
233395		Vimmer	Segway (COI19_segway)	C++14	0 / 100	5 ms	384 KiB

segway

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

#define sz(x) ll(x.size())
#define base 1000000
#define M ll(1e9+7)
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

bool mkr[1005];

set <int> se;

int pos[3][1005];

void dfs(int v)
{
    if (mkr[v]) return;

    mkr[v] = 1;

    vector <int> gr; gr.clear();

    for (auto it : se)
        if (pos[0][v] < pos[0][it] || pos[1][v] < pos[1][it] || pos[2][v] < pos[2][it]) gr.pb(it);

    for (auto it : gr)
    {
        se.erase(it);

        dfs(it);
    }
}
int main()
{
//    freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;

    cin >> n >> q;

    int a[3][n];

    for (int j = 0; j < 3; j++)
        for (int i = 0; i < n; i++) {cin >> a[j][i]; a[j][i]--; pos[j][a[j][i]] = i;}

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

        cin >> tp;

        if (tp == 2)
        {
            int j;

            cin >> j; j--;

            int f, s;

            cin >> f >> s; f--; s--;

            swap(pos[j][f], pos[j][s]);

            a[j][pos[j][f]] = f;

            a[j][pos[j][s]] = s;
        }
        else
        {
            int x;

            cin >> x;

            x--;

            memset(mkr, 0, sizeof(mkr));

            for (int i = 0; i < n; i++) if (i != x) se.insert(i);

            dfs(x);

            if (sz(se) == 0) cout << "DA" << endl;
              else cout << "NE" << endl;
        }
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45