oj.uz

Submission #603359

# Submission time Handle Problem Language Result Execution time Memory
603359 2022-07-24T05:07:33 Z 반딧불(#8427) Synchronization (JOI13_synchronization) C++17
30 / 100
 111 ms 28756 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int x, y, idx;
    Edge(){}
    Edge(int x, int y, int idx): x(x), y(y), idx(idx){}
};

int n, m, q;
int ex[100002], ey[100002];
vector<Edge> link[100002];
int arr[200002];
int query[100002];
vector<int> toggle[100002];
int ans;

void dfs(int x, int p=-1, int t=m){
    ans++;
    for(Edge e: link[x]){
        if(e.y==p || toggle[e.idx].empty() || toggle[e.idx][0] > t) continue;
        int pnt = lower_bound(toggle[e.idx].begin(), toggle[e.idx].end(), t) - toggle[e.idx].begin();
        if(pnt%2){ /// �������� ���
            dfs(e.y, x, min(t, toggle[e.idx][pnt] - 1));
        }
        else{ /// �����ϴ� ���
            if(toggle[e.idx][pnt] == t) dfs(e.y, x, t);
            else if(pnt == 0) continue;
            else dfs(e.y, x, toggle[e.idx][pnt-1]-1);
        }
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<n; i++){
        scanf("%d %d", &ex[i], &ey[i]);
        link[ex[i]].push_back(Edge(ex[i], ey[i], i));
        link[ey[i]].push_back(Edge(ey[i], ex[i], i));
    }
    for(int i=1; i<=m; i++){
        scanf("%d", &arr[i]);
        toggle[arr[i]].push_back(i);
    }
    for(int i=1; i<=q; i++) scanf("%d", &query[i]);

    assert(q==1);

    for(int i=1; i<n; i++) if(toggle[i].size() % 2) toggle[i].push_back(m+1);
    dfs(query[1]);
    printf("%d", ans);
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d %d", &ex[i], &ey[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:48:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     for(int i=1; i<=q; i++) scanf("%d", &query[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 10 ms 5972 KB Output is correct
8 Correct 10 ms 5972 KB Output is correct
9 Correct 10 ms 6080 KB Output is correct
10 Correct 79 ms 15860 KB Output is correct
11 Correct 111 ms 15952 KB Output is correct
12 Correct 76 ms 14756 KB Output is correct
13 Correct 71 ms 15548 KB Output is correct
14 Correct 87 ms 15272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18920 KB Output is correct
2 Correct 57 ms 17340 KB Output is correct
3 Correct 53 ms 19860 KB Output is correct
4 Correct 62 ms 18992 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 28756 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -