oj.uz

Submission #603464

# Submission time Handle Problem Language Result Execution time Memory
603464 2022-07-24T07:21:42 Z 박상훈(#8426) Synchronization (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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