oj.uz

답안 #558441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558441 2022-05-07T10:18:56 Z Yazan_Alattar Tenis (COI19_tenis) C++14
21 / 100
 169 ms 19524 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define aint(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

stack <int> st;
vector <int> adj[M], revadj[M];
int n, q, a[5][M], in[M],comp[M], comps;
bool vist[M];

void dfs(int node){
    vist[node] = 1;
    for(auto i : adj[node]) if(!vist[i]) dfs(i);

    st.push(node);
    return;
}

void revdfs(int node){
    vist[node] = 1;
    comp[node] = comps;

    for(auto i : revadj[node]) if(!vist[i]) revdfs(i);
    return;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= 3; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> a[i][j];

            if(j > 1){
                adj[a[i][j - 1]].pb(a[i][j]);
                revadj[a[i][j]].pb(a[i][j - 1]);
            }
        }
    }

    for(int i = 1; i <= n; ++i) if(!vist[i]) dfs(i);
    for(int i = 1; i <= n; ++i) vist[i] = 0;

    while(st.size()){
        int node = st.top();
        st.pop();
        if(vist[node]) continue;

        ++comps;
        revdfs(node);
    }

    for(int i = 1; i <= 3; ++i){
        for(int j = 1; j < n; ++j){
            int x = comp[a[i][j]], y = comp[a[i][j + 1]];
            if(x != y) ++in[y];
        }
    }

    while(q--){
        int type;
        cin >> type;

        if(type == 1){
            int x;
            cin >> x;

            if(!in[comp[x]]) cout << "DA\n";
            else cout << "NE\n";
        }

        else{
            int x, y, z;
            cin >> x >> y >> z;
        }
    }
    return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 14768 KB Output is correct
2 Correct 146 ms 18508 KB Output is correct
3 Correct 137 ms 18604 KB Output is correct
4 Correct 106 ms 19524 KB Output is correct
5 Correct 113 ms 17520 KB Output is correct
6 Correct 111 ms 18504 KB Output is correct
7 Correct 127 ms 17492 KB Output is correct
8 Correct 144 ms 18928 KB Output is correct
9 Correct 113 ms 18620 KB Output is correct
10 Correct 117 ms 18252 KB Output is correct
11 Correct 114 ms 17596 KB Output is correct
12 Correct 105 ms 19004 KB Output is correct
13 Correct 129 ms 18792 KB Output is correct
14 Correct 131 ms 19068 KB Output is correct
15 Correct 169 ms 19464 KB Output is correct

Subtask #5
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -