oj.uz

Submission #86793

# Submission time Handle Problem Language Result Execution time Memory
86793 2018-11-27T14:53:36 Z vanbang9710 Synchronization (JOI13_synchronization) C++14
100 / 100
 196 ms 13392 KB 
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstring>
#include<iomanip>
#include<string>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<algorithm>
#include<functional>
#include<chrono>
//#include<windows.h>
//#include<direct.h>
#include<random>
#include<sstream>

#define y0 asdahsdlkahsdad
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define taskname "Synchronization"
//#define GuiltiaSinJurai

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

inline void Cin(int &x)
{
    register char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar());
    for (x = 0; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

const int maxN = 1e5 + 1;

static int val[maxN << 2], u[maxN], v[maxN], ans[maxN], last[maxN], st[maxN], en[maxN], et[maxN];
static int n, m, q, Time, lim, threshold, pos, value;
vector<int> adj[maxN];
static bitset<maxN> state;

inline void DFS(int u)
{
    st[u] = ++Time;
    et[Time] = u;
    for (int v : adj[u])
        if (st[v] == 0) DFS(v);
    en[u] = Time;
}
void Inp()
{
    Cin(n); Cin(m); Cin(q);
    for (int i = 1; i < n; ++i)
    {
        Cin(u[i]); Cin(v[i]);
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    DFS(1);
}

#define mid (l + r >> 1)
inline void Build(int x, int l, int r)
{
    if (l == r) { val[x] = en[et[l]]; return; }
    Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
    val[x] = max(val[x << 1], val[x << 1 | 1]);
}
inline void _Update(int x, int l, int r)
{
    if (l == r) { val[x] = value; return; }
    if (pos <= mid) _Update(x << 1, l, mid);
    else _Update(x << 1 | 1, mid + 1, r);
    val[x] = max(val[x << 1], val[x << 1 | 1]);
}
inline void Update(int a, int b) { pos = a; value = b; _Update(1, 1, n); }
inline int _Query(int x, int l, int r)
{
    if (l > lim || val[x] < threshold) return 0;
    if (l == r) return l;
    int res = _Query(x << 1 | 1, mid + 1, r);
    if (res) return res;
    return _Query(x << 1, l, mid);
}
inline int Query(int a, int b) { lim = a; threshold = b; return et[_Query(1, 1, n)]; }

inline void SwitchEdge(int u, int v)
{
    if (st[u] > st[v]) swap(u, v);
    int root = Query(st[u], en[u]);
    if (state.test(Time))
    {
        ans[v] = last[v] = ans[root];
        Update(st[v], en[v]);
    }
    else
    {
        ans[root] += ans[v] - last[v];
        Update(st[v], 0);
    }
    state.flip(Time);
}
void Solve()
{
    Build(1, 1, n);
    fill_n(ans + 1, n, 1);
    while (--m >= 0)
    {
        Cin(Time);
        SwitchEdge(u[Time], v[Time]);
    }
}

void Print()
{
    while (--q >= 0)
    {
        Cin(Time);
        cout << ans[Query(st[Time], en[Time])] << '\n';
    }
}

int main()
{
    #ifdef GuiltiaSinJurai
    auto start = chrono::steady_clock::now();
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);

    Inp();
    Solve();
    Print();

    #ifdef GuiltiaSinJurai
    auto end = chrono::steady_clock::now();
    cerr << "In milliseconds : "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cerr << '\n' << "In seconds : "
         << chrono::duration_cast<chrono::seconds>(end - start).count() << '\n';
    #endif
    return 0;

}

Compilation message

synchronization.cpp: In function 'void Build(int, int, int)':
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:79:22: note: in expansion of macro 'mid'
     Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
                      ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:79:46: note: in expansion of macro 'mid'
     Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
                                              ^~~
synchronization.cpp: In function 'void _Update(int, int, int)':
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:85:16: note: in expansion of macro 'mid'
     if (pos <= mid) _Update(x << 1, l, mid);
                ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:85:40: note: in expansion of macro 'mid'
     if (pos <= mid) _Update(x << 1, l, mid);
                                        ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:86:30: note: in expansion of macro 'mid'
     else _Update(x << 1 | 1, mid + 1, r);
                              ^~~
synchronization.cpp: In function 'int _Query(int, int, int)':
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:94:34: note: in expansion of macro 'mid'
     int res = _Query(x << 1 | 1, mid + 1, r);
                                  ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:96:30: note: in expansion of macro 'mid'
     return _Query(x << 1, l, mid);
                              ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 13 ms 3568 KB Output is correct
8 Correct 14 ms 3628 KB Output is correct
9 Correct 13 ms 3628 KB Output is correct
10 Correct 171 ms 10020 KB Output is correct
11 Correct 141 ms 10020 KB Output is correct
12 Correct 117 ms 12892 KB Output is correct
13 Correct 99 ms 12892 KB Output is correct
14 Correct 101 ms 12892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12892 KB Output is correct
2 Correct 77 ms 12892 KB Output is correct
3 Correct 66 ms 12892 KB Output is correct
4 Correct 64 ms 12892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 16 ms 12892 KB Output is correct
8 Correct 157 ms 13168 KB Output is correct
9 Correct 157 ms 13168 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 13168 KB Output is correct
2 Correct 86 ms 13392 KB Output is correct
3 Correct 90 ms 13392 KB Output is correct
4 Correct 89 ms 13392 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13392 KB Output is correct
2 Correct 4 ms 13392 KB Output is correct
3 Correct 4 ms 13392 KB Output is correct
4 Correct 4 ms 13392 KB Output is correct
5 Correct 5 ms 13392 KB Output is correct
6 Correct 19 ms 13392 KB Output is correct
7 Correct 196 ms 13392 KB Output is correct
8 Correct 142 ms 13392 KB Output is correct
9 Correct 141 ms 13392 KB Output is correct
10 Correct 116 ms 13392 KB Output is correct
11 Correct 100 ms 13392 KB Output is correct
12 Correct 102 ms 13392 KB Output is correct
13 Correct 99 ms 13392 KB Output is correct