oj.uz

Submission #881927

# Submission time Handle Problem Language Result Execution time Memory
881927 2023-12-02T09:25:38 Z 12345678 Synchronization (JOI13_synchronization) C++17
30 / 100
 58 ms 23128 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, m, q, u, v, on[nx], x, dp[nx];
vector<pair<int, int>> d[nx], t[2*nx];

void dfs(int u, int p, int l)
{
    dp[u]=1;
    for (auto [v, idx]:d[u])
    {
        if (v==p||t[idx].empty()) continue;
        auto itr=lower_bound(t[idx].begin(), t[idx].end(), make_pair(l, INT_MAX));
        if (itr==t[idx].begin()) continue;
        dfs(v, u, min(prev(itr)->second, l));
        dp[u]+=dp[v];
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back({v, i}), d[v].push_back({u, i});
    for (int i=1; i<=m; i++)
    {
        cin>>x;
        if (on[x]) t[x].push_back({on[x], i}), on[x]=0;
        else on[x]=i;
    }
    for (int i=1; i<n; i++) if (on[i]) t[i].push_back({on[i], m});
    cin>>x;
    dfs(x, x, m);
    cout<<dp[x];
}

/*
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
4
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7268 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7504 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 6 ms 8284 KB Output is correct
8 Correct 7 ms 8284 KB Output is correct
9 Correct 6 ms 8284 KB Output is correct
10 Correct 53 ms 16980 KB Output is correct
11 Correct 58 ms 16976 KB Output is correct
12 Correct 39 ms 15964 KB Output is correct
13 Correct 37 ms 16836 KB Output is correct
14 Correct 39 ms 16732 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 21204 KB Output is correct
2 Correct 35 ms 19288 KB Output is correct
3 Correct 34 ms 23128 KB Output is correct
4 Correct 33 ms 22096 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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