제출 #86790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86790		vanbang9710	동기화 (JOI13_synchronization)	C++14	100 / 100	276 ms	13420 KiB

synchronization

#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;

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40