oj.uz

Submission #725745

# Submission time Handle Problem Language Result Execution time Memory
725745 2023-04-18T01:56:09 Z josanneo22 Alternating Heights (CCO22_day1problem1) C++17
11 / 25
 1000 ms 75024 KB 
#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{
        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> ok=find_cycle();
            int yeaaaa=(ok[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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 74336 KB Output is correct
2 Correct 316 ms 74144 KB Output is correct
3 Correct 300 ms 73976 KB Output is correct
4 Correct 170 ms 3644 KB Output is correct
5 Correct 162 ms 3736 KB Output is correct
6 Correct 323 ms 73732 KB Output is correct
7 Correct 382 ms 73720 KB Output is correct
8 Correct 302 ms 74060 KB Output is correct
9 Correct 305 ms 73980 KB Output is correct
10 Correct 321 ms 74188 KB Output is correct
11 Correct 319 ms 74860 KB Output is correct
12 Correct 302 ms 75024 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 1964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 60 ms 580 KB Output is correct
3 Correct 64 ms 608 KB Output is correct
4 Correct 49 ms 70916 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 58 ms 568 KB Output is correct
8 Correct 72 ms 468 KB Output is correct
9 Correct 78 ms 468 KB Output is correct
10 Correct 82 ms 576 KB Output is correct
11 Correct 83 ms 528 KB Output is correct
12 Correct 94 ms 468 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 74336 KB Output is correct
2 Correct 316 ms 74144 KB Output is correct
3 Correct 300 ms 73976 KB Output is correct
4 Correct 170 ms 3644 KB Output is correct
5 Correct 162 ms 3736 KB Output is correct
6 Correct 323 ms 73732 KB Output is correct
7 Correct 382 ms 73720 KB Output is correct
8 Correct 302 ms 74060 KB Output is correct
9 Correct 305 ms 73980 KB Output is correct
10 Correct 321 ms 74188 KB Output is correct
11 Correct 319 ms 74860 KB Output is correct
12 Correct 302 ms 75024 KB Output is correct
13 Execution timed out 1065 ms 1964 KB Time limit exceeded
14 Halted 0 ms 0 KB -