oj.uz

Submission #638578

# Submission time Handle Problem Language Result Execution time Memory
638578 2022-09-06T12:23:59 Z morasha3 Alternating Heights (CCO22_day1problem1) C++17
25 / 25
 868 ms 5020 KB 
#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

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();
      |            ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 3536 KB Output is correct
2 Correct 172 ms 3484 KB Output is correct
3 Correct 191 ms 3532 KB Output is correct
4 Correct 132 ms 3532 KB Output is correct
5 Correct 150 ms 3636 KB Output is correct
6 Correct 215 ms 3568 KB Output is correct
7 Correct 171 ms 3532 KB Output is correct
8 Correct 185 ms 3516 KB Output is correct
9 Correct 222 ms 3648 KB Output is correct
10 Correct 249 ms 4304 KB Output is correct
11 Correct 296 ms 4868 KB Output is correct
12 Correct 366 ms 4852 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 3584 KB Output is correct
2 Correct 182 ms 3640 KB Output is correct
3 Correct 169 ms 3572 KB Output is correct
4 Correct 135 ms 4560 KB Output is correct
5 Correct 179 ms 3788 KB Output is correct
6 Correct 157 ms 3544 KB Output is correct
7 Correct 166 ms 3608 KB Output is correct
8 Correct 184 ms 3600 KB Output is correct
9 Correct 177 ms 3900 KB Output is correct
10 Correct 167 ms 4476 KB Output is correct
11 Correct 165 ms 4568 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 437 ms 588 KB Output is correct
3 Correct 516 ms 468 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 332 ms 428 KB Output is correct
8 Correct 563 ms 468 KB Output is correct
9 Correct 785 ms 468 KB Output is correct
10 Correct 586 ms 560 KB Output is correct
11 Correct 653 ms 468 KB Output is correct
12 Correct 492 ms 588 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 3536 KB Output is correct
2 Correct 172 ms 3484 KB Output is correct
3 Correct 191 ms 3532 KB Output is correct
4 Correct 132 ms 3532 KB Output is correct
5 Correct 150 ms 3636 KB Output is correct
6 Correct 215 ms 3568 KB Output is correct
7 Correct 171 ms 3532 KB Output is correct
8 Correct 185 ms 3516 KB Output is correct
9 Correct 222 ms 3648 KB Output is correct
10 Correct 249 ms 4304 KB Output is correct
11 Correct 296 ms 4868 KB Output is correct
12 Correct 366 ms 4852 KB Output is correct
13 Correct 160 ms 3584 KB Output is correct
14 Correct 182 ms 3640 KB Output is correct
15 Correct 169 ms 3572 KB Output is correct
16 Correct 135 ms 4560 KB Output is correct
17 Correct 179 ms 3788 KB Output is correct
18 Correct 157 ms 3544 KB Output is correct
19 Correct 166 ms 3608 KB Output is correct
20 Correct 184 ms 3600 KB Output is correct
21 Correct 177 ms 3900 KB Output is correct
22 Correct 167 ms 4476 KB Output is correct
23 Correct 165 ms 4568 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 437 ms 588 KB Output is correct
27 Correct 516 ms 468 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 332 ms 428 KB Output is correct
32 Correct 563 ms 468 KB Output is correct
33 Correct 785 ms 468 KB Output is correct
34 Correct 586 ms 560 KB Output is correct
35 Correct 653 ms 468 KB Output is correct
36 Correct 492 ms 588 KB Output is correct
37 Correct 760 ms 4552 KB Output is correct
38 Correct 636 ms 4348 KB Output is correct
39 Correct 195 ms 3748 KB Output is correct
40 Correct 130 ms 5020 KB Output is correct
41 Correct 174 ms 4624 KB Output is correct
42 Correct 562 ms 4476 KB Output is correct
43 Correct 760 ms 4692 KB Output is correct
44 Correct 526 ms 4464 KB Output is correct
45 Correct 868 ms 4904 KB Output is correct
46 Correct 774 ms 4904 KB Output is correct
47 Correct 836 ms 4920 KB Output is correct