Submission #638578

#TimeUsernameProblemLanguageResultExecution timeMemory
638578morasha3Alternating Heights (CCO22_day1problem1)C++17
25 / 25
868 ms5020 KiB
#include <bits/stdc++.h> using namespace std; typedef int ll; typedef double ld; const ll mod=1e9+7; #define endl '\n' bool dfs(vector<vector<int>>& v) { int n = v.size(); vector<int> deg(n); for (int a = 0; a < n; a++) for (int b : v[a]) deg[b]++; vector<int> q; q.reserve(n); for (int i = 0; i < n; i++) if (deg[i] == 0) q.push_back(i); for (int rep = 0; rep < q.size(); rep++) { int c = q[rep]; for (auto nxt : v[c]) { deg[nxt]--; if (deg[nxt] == 0) q.push_back(nxt); } } return n>q.size(); } int32_t main() { //freopen("jumping.in","r",stdin); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,k,q; cin>>n>>k>>q; ll arr[n]; for(int i=0; i<n; i++) {cin>>arr[i]; arr[i]--;} vector<int> can(n); for (int rep : {0, 1}) { for (int l = rep, r = l; l < n; l += 2) { while (r < n) { vector<vector<int>> adj(k); for (int i = l; i < r; i++) { if (i % 2 == l % 2) adj[arr[i]].push_back(arr[i + 1]); else adj[arr[i + 1]].push_back(arr[i]); } if (dfs(adj)) break; r++; } can[l] = r; } } while(q--) { ll a,b; cin>>a>>b; a--,b--; if(can[a]>b) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'bool dfs(std::vector<std::vector<int> >&)':
Main.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int rep = 0; rep < q.size(); rep++)
      |                       ~~~~^~~~~~~~~~
Main.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     return n>q.size();
      |            ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...