oj.uz

Submission #725744

# Submission time Handle Problem Language Result Execution time Memory
725744 2023-04-18T01:53:55 Z josanneo22 Alternating Heights (CCO22_day1problem1) C++17
11 / 25
 1000 ms 80324 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 = 2e5 + 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 319 ms 79372 KB Output is correct
2 Correct 331 ms 79500 KB Output is correct
3 Correct 317 ms 79184 KB Output is correct
4 Correct 149 ms 8820 KB Output is correct
5 Correct 151 ms 8992 KB Output is correct
6 Correct 420 ms 79060 KB Output is correct
7 Correct 352 ms 78904 KB Output is correct
8 Correct 330 ms 79380 KB Output is correct
9 Correct 285 ms 79192 KB Output is correct
10 Correct 355 ms 79424 KB Output is correct
11 Correct 343 ms 80168 KB Output is correct
12 Correct 308 ms 80324 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 56 ms 5220 KB Output is correct
3 Correct 66 ms 5216 KB Output is correct
4 Correct 42 ms 75432 KB Output is correct
5 Correct 4 ms 5024 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 65 ms 5208 KB Output is correct
8 Correct 70 ms 5224 KB Output is correct
9 Correct 79 ms 5208 KB Output is correct
10 Correct 94 ms 5204 KB Output is correct
11 Correct 100 ms 5232 KB Output is correct
12 Correct 90 ms 5204 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 79372 KB Output is correct
2 Correct 331 ms 79500 KB Output is correct
3 Correct 317 ms 79184 KB Output is correct
4 Correct 149 ms 8820 KB Output is correct
5 Correct 151 ms 8992 KB Output is correct
6 Correct 420 ms 79060 KB Output is correct
7 Correct 352 ms 78904 KB Output is correct
8 Correct 330 ms 79380 KB Output is correct
9 Correct 285 ms 79192 KB Output is correct
10 Correct 355 ms 79424 KB Output is correct
11 Correct 343 ms 80168 KB Output is correct
12 Correct 308 ms 80324 KB Output is correct
13 Execution timed out 1037 ms 6216 KB Time limit exceeded
14 Halted 0 ms 0 KB -