oj.uz

Submission #331762

# Submission time Handle Problem Language Result Execution time Memory
331762 2020-11-30T01:38:42 Z HoneyBadger Synchronization (JOI13_synchronization) C++17
100 / 100
 401 ms 33500 KB 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <algorithm>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <ctime>
#include <chrono>


/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
*/


#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else
    #define dbg(x)
#endif

#define int long long
#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a, b) for (int i = a; i < b; i++)
#define fj(a, b) for (int j = a; j < b; j++)
#define fk(a, b) for (int k = a; k < b; k++)
#define fi1(a, b) for (int i = a - 1; i >= b; i--)
#define fj1(a, b) for (int j = a - 1; j >= b; j--)
#define fk1(a, b) for (int k = a - 1; k >= b; k--)
#define fx(x, a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; }

ostream& operator << (ostream &out, const vector<int> &b) {
    for (auto k : b) out << k << ' ';
    return out;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 100500;
const double EPS = 1e-9;
const int PW = 17;

#warning setpw

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int BIT[MX];

int get(int i) {
	int ans = 0;
	for (; i > 0; i -= i&-i)
		ans += BIT[i];
	return ans;
}

void upd(int i, int x) {
	for (; i < MX; i += i&-i)
		BIT[i] += x;
}

void updlr(int l, int r, int x) {
	upd(l, x);
	upd(r, -x);
}

vi g[MX];
vpii edges;
int up[MX][PW];
int tin[MX], tout[MX], timer = 1;

void dfs(int v, int pr) {
	up[v][0] = pr;
	fi(1, PW) up[v][i] = up[up[v][i - 1]][i - 1];
	tin[v] = timer++;

	fx(to, g[v]) {
		if (to == pr) continue;
		dfs(to, v);
	}
	tout[v] = timer;
}

int sum(int v) {
	return get(tin[v]);
}

int getp(int v) {
	for (int i = PW - 1; i >= 0; --i) {
		//cout << v << ' ' << up[v][i] << ' ' << sum(v) << ' ' << sum(up[v][i]) << '\n';
		if (sum(v) - sum(up[v][i]) == (1 << i)) {
			v = up[v][i];
		}
	}
	return v;
}

int cnt[MX];
int delta[MX];


void delle(int v) {
	updlr(tin[v], tout[v], -1);
}

void adde(int v) {
	updlr(tin[v], tout[v], 1);
}

void del(int v) {
	//cout << "del : " << v << endl;
	int p = getp(v);
	//dbg(p);
	cnt[v] = cnt[p];
	delta[v] = 0;
	delle(v);
}

void add(int v) {
	adde(v);
	//cout << "add : " << v << endl;
	int p = getp(v);
	//dbg(p);
	delta[p] += delta[v];
	cnt[p] += delta[v];
	delta[v] = 0;
} 

int val[MX];

void flip(int i) {
	if (val[i] == 1)
		del(i);
	else
		add(i);
	val[i] ^= 1;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, q;
    cin >> n >> m >> q;
    fi(1, n) {
    	int a, b;
    	cin >> a >> b;
    	--a, --b;
    	edges.pb({a, b});
    	g[a].pb(b);
    	g[b].pb(a);
    }
    fi(0, n) {
    	cnt[i] = delta[i] = 1;
    }
    dfs(0, 0);

    while (m--) {
    	int d;
    	cin >> d;
    	--d;
    	auto[a, b] = edges[d];
    	if (tin[a] < tin[b]) swap(a, b);
    	flip(a);
    	/*fi(0, n) {
    		cout << cnt[i] << ' ' << delta[i] << '\n';
    	}*/
    }

    while (q--) {
    	int v;
    	cin >> v;
    	--v;
    	cout << cnt[getp(v)] << '\n'; 
    }
}

Compilation message

synchronization.cpp:88:2: warning: #warning setpw [-Wcpp]
   88 | #warning setpw
      |  ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 3052 KB Output is correct
7 Correct 17 ms 5224 KB Output is correct
8 Correct 17 ms 5224 KB Output is correct
9 Correct 17 ms 5224 KB Output is correct
10 Correct 296 ms 28512 KB Output is correct
11 Correct 294 ms 28540 KB Output is correct
12 Correct 319 ms 32476 KB Output is correct
13 Correct 195 ms 28124 KB Output is correct
14 Correct 192 ms 27740 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 30172 KB Output is correct
2 Correct 118 ms 29916 KB Output is correct
3 Correct 135 ms 31836 KB Output is correct
4 Correct 126 ms 31964 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2924 KB Output is correct
6 Correct 4 ms 3052 KB Output is correct
7 Correct 24 ms 5736 KB Output is correct
8 Correct 378 ms 33244 KB Output is correct
9 Correct 401 ms 33500 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 33244 KB Output is correct
2 Correct 191 ms 32860 KB Output is correct
3 Correct 194 ms 33116 KB Output is correct
4 Correct 191 ms 33116 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 4 ms 3052 KB Output is correct
6 Correct 23 ms 5352 KB Output is correct
7 Correct 359 ms 29548 KB Output is correct
8 Correct 386 ms 33372 KB Output is correct
9 Correct 241 ms 29276 KB Output is correct
10 Correct 246 ms 29148 KB Output is correct
11 Correct 167 ms 31452 KB Output is correct
12 Correct 159 ms 31452 KB Output is correct
13 Correct 194 ms 33116 KB Output is correct