oj.uz

답안 #603464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603464 2022-07-24T07:21:42 Z 박상훈(#8426) 동기화 (JOI13_synchronization) C++17
30 / 100
 77 ms 14580 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Edge{
    int v, l, r;
    Edge(){}
    Edge(int _v, int _l, int _r): v(_v), l(_l), r(_r) {}
    bool operator<(const Edge &E)const{
        return r > E.r;
    }
};
int A[100100], B[100100], on[100100], prv[100100], ans;
vector<Edge> adj[100100];
bool visited[100100];

void dfs(int s, int t, int pa = -1){
    if (visited[s]) return;
    ans++;
    visited[s] = 1;
    sort(adj[s].begin(), adj[s].end());
    for (auto &[v, l, r]:adj[s]) if (v!=pa){
        if (l<=t){
            dfs(v, min(r, t), s);
        }
    }
}

int main(){
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    for (int i=1;i<=n-1;i++){
        scanf("%d %d", A+i, B+i);
    }

    for (int i=1;i<=m;i++){
        int x;
        scanf("%d", &x);
        if (on[x]){
            adj[A[x]].emplace_back(B[x], prv[x], i-1);
            adj[B[x]].emplace_back(A[x], prv[x], i-1);


            //printf(" %d %d %d\n", A[x], B[x], i);
        }
        else{
            prv[x] = i;
        }
        on[x] ^= 1;
    }

    for (int i=1;i<=n-1;i++) if (on[i]){
        adj[A[i]].emplace_back(B[i], prv[i], m);
        adj[B[i]].emplace_back(A[i], prv[i], m);

    }

    int s;
    scanf("%d", &s);
    dfs(s, m);
    printf("%d\n", ans);
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d %d", A+i, B+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d", &s);
      |     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 7 ms 3220 KB Output is correct
8 Correct 7 ms 3284 KB Output is correct
9 Correct 9 ms 3284 KB Output is correct
10 Correct 77 ms 9016 KB Output is correct
11 Correct 71 ms 9084 KB Output is correct
12 Correct 75 ms 9236 KB Output is correct
13 Correct 61 ms 8572 KB Output is correct
14 Correct 60 ms 8500 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 13180 KB Output is correct
2 Correct 53 ms 11224 KB Output is correct
3 Correct 42 ms 14580 KB Output is correct
4 Correct 41 ms 13428 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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