oj.uz

Submission #86792

# Submission time Handle Problem Language Result Execution time Memory
86792 2018-11-27T14:39:38 Z vanbang9710 Synchronization (JOI13_synchronization) C++14
100 / 100
 209 ms 13332 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 2680 KB Output is correct
2 Correct 5 ms 2804 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2880 KB Output is correct
5 Correct 4 ms 2956 KB Output is correct
6 Correct 6 ms 3032 KB Output is correct
7 Correct 15 ms 3672 KB Output is correct
8 Correct 15 ms 3688 KB Output is correct
9 Correct 16 ms 3688 KB Output is correct
10 Correct 167 ms 10120 KB Output is correct
11 Correct 153 ms 10120 KB Output is correct
12 Correct 134 ms 13020 KB Output is correct
13 Correct 112 ms 13020 KB Output is correct
14 Correct 102 ms 13020 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 13020 KB Output is correct
2 Correct 81 ms 13020 KB Output is correct
3 Correct 72 ms 13020 KB Output is correct
4 Correct 72 ms 13020 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13020 KB Output is correct
2 Correct 4 ms 13020 KB Output is correct
3 Correct 4 ms 13020 KB Output is correct
4 Correct 4 ms 13020 KB Output is correct
5 Correct 4 ms 13020 KB Output is correct
6 Correct 5 ms 13020 KB Output is correct
7 Correct 17 ms 13020 KB Output is correct
8 Correct 152 ms 13204 KB Output is correct
9 Correct 171 ms 13204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 13204 KB Output is correct
2 Correct 94 ms 13296 KB Output is correct
3 Correct 92 ms 13332 KB Output is correct
4 Correct 101 ms 13332 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13332 KB Output is correct
2 Correct 4 ms 13332 KB Output is correct
3 Correct 4 ms 13332 KB Output is correct
4 Correct 4 ms 13332 KB Output is correct
5 Correct 6 ms 13332 KB Output is correct
6 Correct 19 ms 13332 KB Output is correct
7 Correct 209 ms 13332 KB Output is correct
8 Correct 161 ms 13332 KB Output is correct
9 Correct 150 ms 13332 KB Output is correct
10 Correct 147 ms 13332 KB Output is correct
11 Correct 109 ms 13332 KB Output is correct
12 Correct 112 ms 13332 KB Output is correct
13 Correct 95 ms 13332 KB Output is correct