oj.uz

Submission #701645

# Submission time Handle Problem Language Result Execution time Memory
701645 2023-02-21T16:26:58 Z sugartheanh Synchronization (JOI13_synchronization) C++14
30 / 100
 84 ms 23792 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;
#define ii pair<int,int>
#define fi first
#define se second
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
int n,m,q,d[N],first[N],ans = 0;
vector<ii>p[N],c[N];
bool on[N];
int getpos(int k,int last)
{
    int l = 0,r = c[k].size()-1;
    int pos = -1;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(c[k][mid].fi < last)
        {
            pos = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return pos;
}
void dfs(int x,int u,int last)
{
    ans++;
    for(auto v : p[u])
    {
        if(v.fi == x)
            continue;
        int pos = getpos(v.se, last);
        if(pos == -1)
            continue;
        dfs(u,v.fi ,min(last, c[v.se][pos].se));
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>q;
    for(int i = 1;i < n;i++)
    {
        int u,v;
        cin>>u>>v;
        p[u].push_back(ii(v,i));
        p[v].push_back(ii(u,i));
    }
    for(int i = 1;i <= m;i++)
    {
        int x;
        cin>>x;
        if(!on[x])
            first[x] = i;
        else
            c[x].push_back(ii(first[x], i));
        on[x] ^= 1;
    }
    for(int i = 1;i < n;i++)
    {
        if(on[i])
            c[i].push_back(ii(first[i], m+1));
    }
    while(q--)
    {
        int root;
        cin>>root;
        dfs(0,root,m+1);
        cout<<ans;
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int getpos(int, int)':
synchronization.cpp:19:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9712 KB Output is correct
6 Correct 6 ms 9736 KB Output is correct
7 Correct 10 ms 10580 KB Output is correct
8 Correct 10 ms 10504 KB Output is correct
9 Correct 10 ms 10540 KB Output is correct
10 Correct 72 ms 19080 KB Output is correct
11 Correct 64 ms 19020 KB Output is correct
12 Correct 55 ms 18352 KB Output is correct
13 Correct 51 ms 18808 KB Output is correct
14 Correct 56 ms 18764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 22312 KB Output is correct
2 Correct 50 ms 20788 KB Output is correct
3 Correct 43 ms 23792 KB Output is correct
4 Correct 42 ms 23008 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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