oj.uz

Submission #603371

# Submission time Handle Problem Language Result Execution time Memory
603371 2022-07-24T05:37:00 Z 이동현(#8430) Synchronization (JOI13_synchronization) C++17
30 / 100
 166 ms 43012 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int NS = (int)2e5 + 4;

int n, m, q;
vector<vector<int>> way[NS];
vector<int> a[NS];
int lst[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        a[i].resize(2);
        cin >> a[i][0] >> a[i][1];
    }
    for(int i = 1; i <= m; ++i){
        int x; cin >> x;
        if(lst[x]){
            way[a[x][0]].push_back({a[x][1], lst[x], i});
            way[a[x][1]].push_back({a[x][0], lst[x], i});
            lst[x] = 0;
        }
        else{
            lst[x] = i;
        }
    }
    int qp; cin >> qp;
    for(int i = 1; i < n; ++i){
        if(lst[i]){
            way[a[i][0]].push_back({a[i][1], lst[i], m + 1});
            way[a[i][1]].push_back({a[i][0], lst[i], m + 1});
        }
    }
    priority_queue<vector<int>> pq;
    vector<int> ans(n + 1, -1);
    pq.push({m + 1, qp});
    while(!pq.empty()){
        int t = pq.top()[0], id = pq.top()[1];
        pq.pop();
        if(ans[id] != -1){
            continue;
        }
        ans[id] = t;
        for(auto&nxt:way[id]){
            if(nxt[1] <= t){
                pq.push({min(nxt[2], t), nxt[0]});
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        if(ans[i] != -1){
            ++cnt;
        }
    }
    cout << cnt << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9748 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 13 ms 11732 KB Output is correct
8 Correct 13 ms 11720 KB Output is correct
9 Correct 14 ms 11796 KB Output is correct
10 Correct 125 ms 30300 KB Output is correct
11 Correct 123 ms 30548 KB Output is correct
12 Correct 98 ms 30412 KB Output is correct
13 Correct 166 ms 34580 KB Output is correct
14 Correct 157 ms 27532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 43012 KB Output is correct
2 Correct 125 ms 38516 KB Output is correct
3 Correct 61 ms 27476 KB Output is correct
4 Correct 87 ms 28420 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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