oj.uz

Submission #611745

# Submission time Handle Problem Language Result Execution time Memory
611745 2022-07-29T07:05:15 Z 반딧불(#8497) Tenis (COI19_tenis) C++17
21 / 100
 154 ms 21916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q, k;
int a[100002], b[100002], c[100002];
vector<int> link[100002], revLink[100002];
int sccNum[100002];
stack<int> sccStk;
bool visited[100002];
vector<int> sccLink[100002];
int inDeg[100002];
bool ans[100002];

void sccDfs1(int x){
    visited[x] = 1;
    for(auto y: link[x]){
        if(visited[y]) continue;
        sccDfs1(y);
    }
    sccStk.push(x);
}

void sccDfs2(int x, int g){
    visited[x] = 0;
    sccNum[x] = g;
    for(auto y: revLink[x]){
        if(!visited[y]) continue;
        sccDfs2(y, g);
    }
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++) scanf("%d", &b[i]);
    for(int i=1; i<=n; i++) scanf("%d", &c[i]);

    for(int i=1; i<n; i++){
        link[a[i]].push_back(a[i+1]);
        link[b[i]].push_back(b[i+1]);
        link[c[i]].push_back(c[i+1]);
    }
    for(int i=1; i<=n; i++) for(auto x: link[i]) revLink[x].push_back(i);
    for(int i=1; i<=n; i++){
        if(!visited[i]) sccDfs1(i);
    }
    while(!sccStk.empty()){
        int x = sccStk.top(); sccStk.pop();
        if(!visited[x]) continue;
        sccDfs2(x, ++k);
    }

    for(int i=1; i<=n; i++){
        for(auto j: link[i]){
            if(sccNum[i] == sccNum[j]) continue;
            sccLink[sccNum[i]].push_back(sccNum[j]);
            inDeg[sccNum[j]]++;
        }
    }

    vector<int> vec;
    for(int i=1; i<=k; i++){
        if(!inDeg[i]) vec.push_back(i);
    }

    if((int)vec.size() == 1){
        for(int i=1; i<=n; i++) if(!inDeg[sccNum[i]]) ans[i] = 1;
    }

    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%s\n", ans[y] ? "DA" : "NE");
    }
}

Compilation message

tenis.cpp: In function 'int main()':
tenis.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tenis.cpp:37:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     for(int i=1; i<=n; i++) scanf("%d", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~
tenis.cpp:38:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     for(int i=1; i<=n; i++) scanf("%d", &b[i]);
      |                             ~~~~~^~~~~~~~~~~~~
tenis.cpp:39:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     for(int i=1; i<=n; i++) scanf("%d", &c[i]);
      |                             ~~~~~^~~~~~~~~~~~~
tenis.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 16852 KB Output is correct
2 Correct 121 ms 20456 KB Output is correct
3 Correct 150 ms 20368 KB Output is correct
4 Correct 149 ms 21916 KB Output is correct
5 Correct 151 ms 19624 KB Output is correct
6 Correct 119 ms 20992 KB Output is correct
7 Correct 125 ms 19400 KB Output is correct
8 Correct 152 ms 21320 KB Output is correct
9 Correct 154 ms 20420 KB Output is correct
10 Correct 149 ms 20008 KB Output is correct
11 Correct 130 ms 19552 KB Output is correct
12 Correct 131 ms 20608 KB Output is correct
13 Correct 143 ms 20144 KB Output is correct
14 Correct 151 ms 20480 KB Output is correct
15 Correct 132 ms 20824 KB Output is correct

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -