oj.uz

답안 #603359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603359 2022-07-24T05:07:33 Z 반딧불(#8427) 동기화 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -