oj.uz

Submission #725755

# Submission time Handle Problem Language Result Execution time Memory
725755 2023-04-18T02:33:02 Z josanneo22 Alternating Heights (CCO22_day1problem1) C++17
11 / 25
 297 ms 75600 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 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 i=0;i<n;i++){
            for(int j=0;j<n;j++){
                adj[j].clear();
            }
            ok[i][i]=1;
            int cnt=1;
            if(i+1<n){
                adj[a[i]].push_back(a[i+1]);
            }
            for(int j=i+1;j<n;j++){
                if(cnt%2==0){
                    if(j-1>=0){adj[a[j]].push_back(a[j-1]);
                    }
                }
                cnt++;
                vector<int> meow=find_cycle();
                int yeaaaa=(meow[0]==-1);
                if(yeaaaa){
                    ok[i][j]|=ok[i][j-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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 75020 KB Output is correct
2 Correct 268 ms 74628 KB Output is correct
3 Correct 277 ms 74448 KB Output is correct
4 Correct 113 ms 4052 KB Output is correct
5 Correct 129 ms 4300 KB Output is correct
6 Correct 269 ms 74320 KB Output is correct
7 Correct 262 ms 74248 KB Output is correct
8 Correct 279 ms 74648 KB Output is correct
9 Correct 285 ms 74460 KB Output is correct
10 Correct 297 ms 74768 KB Output is correct
11 Correct 289 ms 75416 KB Output is correct
12 Correct 282 ms 75600 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 6920 KB Output isn't correct
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 54 ms 604 KB Output is correct
3 Correct 59 ms 712 KB Output is correct
4 Correct 36 ms 70884 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 55 ms 468 KB Output is correct
8 Correct 62 ms 576 KB Output is correct
9 Correct 73 ms 584 KB Output is correct
10 Correct 80 ms 468 KB Output is correct
11 Correct 81 ms 596 KB Output is correct
12 Correct 79 ms 504 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 75020 KB Output is correct
2 Correct 268 ms 74628 KB Output is correct
3 Correct 277 ms 74448 KB Output is correct
4 Correct 113 ms 4052 KB Output is correct
5 Correct 129 ms 4300 KB Output is correct
6 Correct 269 ms 74320 KB Output is correct
7 Correct 262 ms 74248 KB Output is correct
8 Correct 279 ms 74648 KB Output is correct
9 Correct 285 ms 74460 KB Output is correct
10 Correct 297 ms 74768 KB Output is correct
11 Correct 289 ms 75416 KB Output is correct
12 Correct 282 ms 75600 KB Output is correct
13 Incorrect 216 ms 6920 KB Output isn't correct
14 Halted 0 ms 0 KB -