Submission #55701032

---

Source Code Expand

#include <bits/stdc++.h>
//#include <bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;

#define FOR_(i,s,e,d) for(int i = s; i < e; i+=d)
#define rep(i,s,e) FOR_(i,s,e,1)
#define rep2(i,s,e) for(int i = s; i >= e; i--)

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

using vi =  vector<int>;
using vii = vector<vector<int>>;
using pii = pair<int,int>;
using ll = long long;
using vll = vector<ll>;
// using ost = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
std::istream& operator>>(std::istream& in, vector<T>& arr) {
    for (T& t: arr) cin >> t;
    return in;
}

void fast_io() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
}

int V, E, Q;
vector<pair<int,int>> colors;
vector<int> deg;
vector<vector<int>> g;


int main() {
    fast_io(); cin >> V >> E;
    deg.assign(V,0); colors.assign(V, {0,1}); g.assign(V, {});

    for (int i = 0, u, v; i < E; i++) {
        cin >> u >> v; u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    const int SQRT_E = sqrt(E);
    for (int cur = 0; cur < V; cur++) sort(g[cur].begin(), g[cur].end(), [&](const int u, const int v) { return deg[u] > deg[v]; });

    cin >> Q;
    const auto node_is_heavy = [&](int node) { return deg[node] >= SQRT_E;};
    for (int q = 1, x , col; q <= Q; q++) {
        cin >> x >> col; x--;
        // get last color
        pair<int,int> cur_color = colors[x];
        for (int child: g[x]) {
            if (!node_is_heavy(child)) break;
            if (colors[child].first > abs(cur_color.first)) cur_color = colors[child];
        }

        cout << cur_color.second << '\n';

        colors[x] = {q, col};
        if (node_is_heavy(x)) continue;
        for (int child: g[x]) colors[child] = {-q,col};
    }
}

Submission Info

Judge Result