oj.uz

Submission #86794

# Submission time Handle Problem Language Result Execution time Memory
86794 2018-11-27T14:55:49 Z vanbang9710 Synchronization (JOI13_synchronization) C++14
100 / 100
 187 ms 13424 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);
    for (int i = 1; i < n; ++i)
        if (st[u[i]] > st[v[i]]) swap(u[i], v[i]);
}

#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)
{
    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:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:81:22: note: in expansion of macro 'mid'
     Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
                      ^~~
synchronization.cpp:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:81: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:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:87:16: note: in expansion of macro 'mid'
     if (pos <= mid) _Update(x << 1, l, mid);
                ^~~
synchronization.cpp:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:87:40: note: in expansion of macro 'mid'
     if (pos <= mid) _Update(x << 1, l, mid);
                                        ^~~
synchronization.cpp:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:88: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:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:96:34: note: in expansion of macro 'mid'
     int res = _Query(x << 1 | 1, mid + 1, r);
                                  ^~~
synchronization.cpp:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:98: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 2680 KB Output is correct
2 Correct 4 ms 2932 KB Output is correct
3 Correct 4 ms 2932 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 4 ms 2932 KB Output is correct
6 Correct 4 ms 2960 KB Output is correct
7 Correct 14 ms 3608 KB Output is correct
8 Correct 13 ms 3608 KB Output is correct
9 Correct 14 ms 3744 KB Output is correct
10 Correct 159 ms 10004 KB Output is correct
11 Correct 138 ms 10004 KB Output is correct
12 Correct 119 ms 12908 KB Output is correct
13 Correct 94 ms 12908 KB Output is correct
14 Correct 95 ms 12908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12908 KB Output is correct
2 Correct 73 ms 12908 KB Output is correct
3 Correct 64 ms 12908 KB Output is correct
4 Correct 66 ms 12908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12908 KB Output is correct
2 Correct 4 ms 12908 KB Output is correct
3 Correct 4 ms 12908 KB Output is correct
4 Correct 3 ms 12908 KB Output is correct
5 Correct 4 ms 12908 KB Output is correct
6 Correct 5 ms 12908 KB Output is correct
7 Correct 15 ms 12908 KB Output is correct
8 Correct 145 ms 13180 KB Output is correct
9 Correct 145 ms 13196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 13196 KB Output is correct
2 Correct 95 ms 13424 KB Output is correct
3 Correct 96 ms 13424 KB Output is correct
4 Correct 86 ms 13424 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13424 KB Output is correct
2 Correct 4 ms 13424 KB Output is correct
3 Correct 5 ms 13424 KB Output is correct
4 Correct 4 ms 13424 KB Output is correct
5 Correct 5 ms 13424 KB Output is correct
6 Correct 17 ms 13424 KB Output is correct
7 Correct 187 ms 13424 KB Output is correct
8 Correct 145 ms 13424 KB Output is correct
9 Correct 119 ms 13424 KB Output is correct
10 Correct 127 ms 13424 KB Output is correct
11 Correct 107 ms 13424 KB Output is correct
12 Correct 105 ms 13424 KB Output is correct
13 Correct 85 ms 13424 KB Output is correct