oj.uz

Submission #745679

# Submission time Handle Problem Language Result Execution time Memory
745679 2023-05-21T00:57:46 Z 반딧불(#9962) Alternating Heights (CCO22_day1problem1) C++17
25 / 25
 598 ms 13864 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k, q;
int arr[3002];
int lim[3002];

vector<int> link[3002];
int deg[3002];

bool able(int l, int r){
    for(int i=1; i<=n; i++) link[i].clear(), deg[i]=0;
    for(int i=l, dir=0; i<r; i++, dir=!dir){
        if(dir==0) link[arr[i]].push_back(arr[i+1]), deg[arr[i+1]]++;
        else       link[arr[i+1]].push_back(arr[i]), deg[arr[i]]++;
    }

    queue<int> que;
    for(int i=1; i<=n; i++) if(!deg[i]) que.push(i);
    while(!que.empty()){
        int x = que.front(); que.pop();
        for(auto y: link[x]){
            deg[y]--;
            if(!deg[y]) que.push(y);
        }
    }
    for(int i=1; i<=n; i++) if(deg[i]) return false;
    return true;
}

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
    }
    for(int a=1, b=1; a<=n && b<=n; ){
        if(able(a, b)){
            if(b==n) lim[a] = n, a++;
            else b++;
        }
        else{
            lim[a] = b-1, a++;
            if(a>b) b++;
        }
    }
    for(int i=1; i<=q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%s\n", lim[l] >= r ? "YES" : "NO");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 8396 KB Output is correct
2 Correct 371 ms 8264 KB Output is correct
3 Correct 386 ms 8372 KB Output is correct
4 Correct 219 ms 7192 KB Output is correct
5 Correct 229 ms 8288 KB Output is correct
6 Correct 393 ms 8248 KB Output is correct
7 Correct 392 ms 8372 KB Output is correct
8 Correct 377 ms 8220 KB Output is correct
9 Correct 381 ms 8532 KB Output is correct
10 Correct 428 ms 8816 KB Output is correct
11 Correct 484 ms 9328 KB Output is correct
12 Correct 447 ms 9224 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 8328 KB Output is correct
2 Correct 257 ms 10992 KB Output is correct
3 Correct 256 ms 10960 KB Output is correct
4 Correct 211 ms 8268 KB Output is correct
5 Correct 275 ms 9328 KB Output is correct
6 Correct 259 ms 10980 KB Output is correct
7 Correct 238 ms 11024 KB Output is correct
8 Correct 247 ms 11000 KB Output is correct
9 Correct 247 ms 11388 KB Output is correct
10 Correct 244 ms 11960 KB Output is correct
11 Correct 245 ms 11968 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 0 ms 340 KB Output is correct
2 Correct 206 ms 516 KB Output is correct
3 Correct 224 ms 572 KB Output is correct
4 Correct 130 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 195 ms 472 KB Output is correct
8 Correct 273 ms 604 KB Output is correct
9 Correct 316 ms 496 KB Output is correct
10 Correct 336 ms 572 KB Output is correct
11 Correct 350 ms 460 KB Output is correct
12 Correct 292 ms 472 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 8396 KB Output is correct
2 Correct 371 ms 8264 KB Output is correct
3 Correct 386 ms 8372 KB Output is correct
4 Correct 219 ms 7192 KB Output is correct
5 Correct 229 ms 8288 KB Output is correct
6 Correct 393 ms 8248 KB Output is correct
7 Correct 392 ms 8372 KB Output is correct
8 Correct 377 ms 8220 KB Output is correct
9 Correct 381 ms 8532 KB Output is correct
10 Correct 428 ms 8816 KB Output is correct
11 Correct 484 ms 9328 KB Output is correct
12 Correct 447 ms 9224 KB Output is correct
13 Correct 257 ms 8328 KB Output is correct
14 Correct 257 ms 10992 KB Output is correct
15 Correct 256 ms 10960 KB Output is correct
16 Correct 211 ms 8268 KB Output is correct
17 Correct 275 ms 9328 KB Output is correct
18 Correct 259 ms 10980 KB Output is correct
19 Correct 238 ms 11024 KB Output is correct
20 Correct 247 ms 11000 KB Output is correct
21 Correct 247 ms 11388 KB Output is correct
22 Correct 244 ms 11960 KB Output is correct
23 Correct 245 ms 11968 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 206 ms 516 KB Output is correct
27 Correct 224 ms 572 KB Output is correct
28 Correct 130 ms 340 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 195 ms 472 KB Output is correct
32 Correct 273 ms 604 KB Output is correct
33 Correct 316 ms 496 KB Output is correct
34 Correct 336 ms 572 KB Output is correct
35 Correct 350 ms 460 KB Output is correct
36 Correct 292 ms 472 KB Output is correct
37 Correct 561 ms 13492 KB Output is correct
38 Correct 473 ms 13244 KB Output is correct
39 Correct 389 ms 12792 KB Output is correct
40 Correct 218 ms 8284 KB Output is correct
41 Correct 250 ms 9656 KB Output is correct
42 Correct 465 ms 13360 KB Output is correct
43 Correct 554 ms 13600 KB Output is correct
44 Correct 454 ms 13436 KB Output is correct
45 Correct 598 ms 13712 KB Output is correct
46 Correct 570 ms 13824 KB Output is correct
47 Correct 593 ms 13864 KB Output is correct