oj.uz

Submission #86790

# Submission time Handle Problem Language Result Execution time Memory
86790 2018-11-27T14:17:44 Z vanbang9710 Synchronization (JOI13_synchronization) C++14
100 / 100
 276 ms 13420 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 (r <= lim)
        while (1)
        {
            if (l == r) return val[x] >= threshold ? l : 0;
            if (val[x << 1 | 1] >= threshold) x = x << 1 | 1, l = mid + 1;
            else x <<= 1, r = mid;
        }
    if (l > lim) return 0;
    return max(_Query(x << 1, l, mid), _Query(x << 1 | 1, mid + 1, r));
}
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:96:67: note: in expansion of macro 'mid'
             if (val[x << 1 | 1] >= threshold) x = x << 1 | 1, l = mid + 1;
                                                                   ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:97:31: note: in expansion of macro 'mid'
             else x <<= 1, r = mid;
                               ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:100:34: note: in expansion of macro 'mid'
     return max(_Query(x << 1, l, mid), _Query(x << 1 | 1, mid + 1, r));
                                  ^~~
synchronization.cpp:75:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
synchronization.cpp:100:59: note: in expansion of macro 'mid'
     return max(_Query(x << 1, l, mid), _Query(x << 1 | 1, mid + 1, r));
                                                           ^~~

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 2888 KB Output is correct
5 Correct 4 ms 2888 KB Output is correct
6 Correct 5 ms 2980 KB Output is correct
7 Correct 18 ms 3620 KB Output is correct
8 Correct 18 ms 3792 KB Output is correct
9 Correct 17 ms 3792 KB Output is correct
10 Correct 208 ms 9952 KB Output is correct
11 Correct 219 ms 9964 KB Output is correct
12 Correct 159 ms 12908 KB Output is correct
13 Correct 98 ms 12908 KB Output is correct
14 Correct 125 ms 12908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 12908 KB Output is correct
2 Correct 91 ms 12908 KB Output is correct
3 Correct 75 ms 12908 KB Output is correct
4 Correct 76 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 5 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 18 ms 12908 KB Output is correct
8 Correct 221 ms 13184 KB Output is correct
9 Correct 217 ms 13244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 13244 KB Output is correct
2 Correct 122 ms 13244 KB Output is correct
3 Correct 110 ms 13420 KB Output is correct
4 Correct 113 ms 13420 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13420 KB Output is correct
2 Correct 4 ms 13420 KB Output is correct
3 Correct 4 ms 13420 KB Output is correct
4 Correct 5 ms 13420 KB Output is correct
5 Correct 5 ms 13420 KB Output is correct
6 Correct 25 ms 13420 KB Output is correct
7 Correct 276 ms 13420 KB Output is correct
8 Correct 238 ms 13420 KB Output is correct
9 Correct 145 ms 13420 KB Output is correct
10 Correct 174 ms 13420 KB Output is correct
11 Correct 132 ms 13420 KB Output is correct
12 Correct 132 ms 13420 KB Output is correct
13 Correct 108 ms 13420 KB Output is correct