oj.uz

Submission #86795

# Submission time Handle Problem Language Result Execution time Memory
86795 2018-11-27T14:57:37 Z vanbang9710 Synchronization (JOI13_synchronization) C++14
100 / 100
 181 ms 13352 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]);
    }
    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();

    #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 2684 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2860 KB Output is correct
4 Correct 4 ms 2880 KB Output is correct
5 Correct 4 ms 2880 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 14 ms 3560 KB Output is correct
8 Correct 14 ms 3564 KB Output is correct
9 Correct 14 ms 3576 KB Output is correct
10 Correct 136 ms 9960 KB Output is correct
11 Correct 142 ms 9960 KB Output is correct
12 Correct 117 ms 12840 KB Output is correct
13 Correct 88 ms 12840 KB Output is correct
14 Correct 98 ms 12840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 12840 KB Output is correct
2 Correct 80 ms 12840 KB Output is correct
3 Correct 77 ms 12840 KB Output is correct
4 Correct 64 ms 12840 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12840 KB Output is correct
2 Correct 4 ms 12840 KB Output is correct
3 Correct 5 ms 12840 KB Output is correct
4 Correct 4 ms 12840 KB Output is correct
5 Correct 4 ms 12840 KB Output is correct
6 Correct 5 ms 12840 KB Output is correct
7 Correct 20 ms 12840 KB Output is correct
8 Correct 147 ms 13180 KB Output is correct
9 Correct 151 ms 13208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13212 KB Output is correct
2 Correct 94 ms 13272 KB Output is correct
3 Correct 85 ms 13276 KB Output is correct
4 Correct 88 ms 13308 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13308 KB Output is correct
2 Correct 4 ms 13308 KB Output is correct
3 Correct 4 ms 13308 KB Output is correct
4 Correct 5 ms 13308 KB Output is correct
5 Correct 5 ms 13308 KB Output is correct
6 Correct 17 ms 13308 KB Output is correct
7 Correct 181 ms 13308 KB Output is correct
8 Correct 145 ms 13308 KB Output is correct
9 Correct 155 ms 13308 KB Output is correct
10 Correct 129 ms 13308 KB Output is correct
11 Correct 108 ms 13308 KB Output is correct
12 Correct 104 ms 13308 KB Output is correct
13 Correct 86 ms 13352 KB Output is correct