Submission #725761

#	Time	Username	Problem	Language	Result	Execution time	Memory
725761		josanneo22	Alternating Heights (CCO22_day1problem1)	C++17	17 / 25	1065 ms	74796 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
    int x = 0, w = 1;
    char ch = getchar();
    for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') w = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return x * w;
}
const int maxn = 3e3 + 4;
int n;
vector<int> adj[maxn];
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;

bool dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs(u))
                return true;
        }
        else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}

vector<int> find_cycle() {
    color.assign(n, 0);
    parent.assign(n, -1);
    cycle_start = -1;
    for (int v = 0; v < n; v++) {
        if (color[v] == 0 && dfs(v))
            break;
    }
    if (cycle_start == -1) {
        return { -1 };
    }
    else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
        reverse(cycle.begin(), cycle.end());
        return cycle;
    }
}
void solve() {
    int k, q; cin >> n >> k >> q;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    if (k == 2) {
        int ok[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ok[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            ok[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (a[j] != a[j - 1]) ok[i][j] |= ok[i][j - 1];
                else {
                    ok[i][j] = 0; break;
                }
            }
        }
        for (int queries = 0; queries < q; queries++) {
            int l, r; cin >> l >> r;
            l--; r--;
            if (ok[l][r]) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    else if (n <= 500 && k <= 5) {
        int ok[n + 5][n + 5];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ok[i][j] = 0;
        for (int f = 0; f < n; f++) {
            for (int s = f + 1; s < n; s++) {
                for (int i = 0; i < n; i++) adj[i].clear();
                int cnt = 0;
                int l = f, r = s;
                for (int i = l; i <= r; i++) {
                    if (cnt % 2 == 1) {
                        if (i - 1 >= l)adj[a[i - 1]].push_back(a[i]);
                        if (i + 1 <= r) adj[a[i + 1]].push_back(a[i]);
                    }
                    else {
                        if (i + 1 <= r) adj[a[i]].push_back(a[i + 1]);
                        if (i - 1 >= l) adj[a[i]].push_back(a[i - 1]);
                    }
                    cnt++;
                }
                vector<int> meow = find_cycle();
                int yeaaaa = (meow[0] == -1);
                if (yeaaaa)ok[l][r] = 1;
            }
        }
        for (int queries = 0; queries < q; queries++) {
            int l, r; cin >> l >> r;
            l--; r--;
            if (ok[l][r]) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    else {
        for (int queries = 0; queries < q; queries++) {
            int l, r; cin >> l >> r;
            l--; r--;
            for (int i = 0; i < n; i++) adj[i].clear();
            int cnt = 0;
            for (int i = l; i <= r; i++) {
                if (cnt % 2 == 1) {
                    if (i - 1 >= l)adj[a[i - 1]].push_back(a[i]);
                    if (i + 1 <= r) adj[a[i + 1]].push_back(a[i]);
                }
                else {
                    if (i + 1 <= r) adj[a[i]].push_back(a[i + 1]);
                    if (i - 1 >= l) adj[a[i]].push_back(a[i - 1]);
                }
                cnt++;
            }
            vector<int> meow = find_cycle();
            int yeaaaa = (meow[0] == -1);
            if (yeaaaa) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tt = 1; //cin>>tt;
    while (tt--) {
        solve();
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 8