oj.uz

Submission #725742

# Submission time Handle Problem Language Result Execution time Memory
725742 2023-04-18T01:52:41 Z josanneo22 Alternating Heights (CCO22_day1problem1) C++17
7 / 25
 1000 ms 6956 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;
	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
0 / 4.0

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

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 59 ms 5220 KB Output is correct
3 Correct 62 ms 5224 KB Output is correct
4 Correct 28 ms 5196 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 5 ms 5028 KB Output is correct
7 Correct 54 ms 5200 KB Output is correct
8 Correct 63 ms 5208 KB Output is correct
9 Correct 73 ms 5208 KB Output is correct
10 Correct 90 ms 5332 KB Output is correct
11 Correct 94 ms 5228 KB Output is correct
12 Correct 82 ms 5204 KB Output is correct

Subtask #4
0 / 8.0

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