oj.uz

답안 #333921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333921 2020-12-08T03:19:55 Z Thistle 동기화 (JOI13_synchronization) C++14
100 / 100
 592 ms 25184 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>
using namespace std;
using ll = long long;
using ld = long double;
using H = pair<ll, ll>;
using P = pair<ll, H>;
using vi = vector<ll>;
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define mkp make_pair
#define vec vector
#define pb emplace_back
#define siz(a) (int)(a).size()
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,num) (lower_bound(all(b),(num))-(b).begin())
#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define cyes printf("Yes\n")
#define cno printf("No\n")
#define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--)
#define gcj printf("Case #%lld: ",qq123_+1)
#define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read()
#define found(a,x) (a.root(x)!=a.end())
constexpr ll mod = (ll)1e9 + 7;
constexpr ll Mod = 998244353;
constexpr ld EPS = 1e-10;
constexpr ll inf = (ll)3 * 1e18;
constexpr int Inf = (ll)15 * 1e8;
constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
bool ina(int t, int l, int r) { return l <= t && t < r; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll ppc(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
void fin1() { printf("-1\n"); exit(0); }
void fin0() { printf("0\n"); exit(0); }
template<typename T>
class csum {
	vec<T> v;
public:
	csum(vec<T>& a) :v(a) { build(); }
	csum() {}
	csum(int sz) { init(sz); }
	void init(int sz) { v = vector<T>(sz, 0); }
	void init(vec<T>& a) { v = a; build(); }
	void build() {
		for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];
	}
	void add(int l, int r, T x) {
		v[l] += x;
		v[r] -= x;
	}//[l,r)
	 //[l,r]
	T a(int l, int r) {
		if (r < l) return 0;
		return v[r] - (l == 0 ? 0 : v[l - 1]);
	}
	//[l,r)
	T b(int l, int r) {
		return a(l, r - 1);
	}
	T a(pair<int, int>t) {
		return a(t.first, t.second);
	}
	T b(pair<int, int>t) {
		return b(t.first, t.second);
	}
	T operator[](int x)const {
		return v[x];
	}
};
template<ll mod>
class modint {
public:ll v;
	   modint(ll v = 0) { s(v % mod + mod); }
	   constexpr static int fn_ = (ll)2e6 + 5;
	   static vector<modint>fact, comp;
	   modint pow(ll x) const {
		   modint b(v), c(1);
		   while (x) {
			   if (x & 1) c *= b;
			   b *= b;
			   x >>= 1;
		   }
		   return c;
	   }
	   inline modint& s(int vv) {
		   v = vv < mod ? vv : vv - mod;
		   return *this;
	   }
	   inline modint inv()const { return pow(mod - 2); }
	   inline modint operator-()const { return modint() - *this; }
	   inline modint& operator+=(const modint b) { return s(v + b.v); }
	   inline modint& operator-=(const modint b) { return s(v + mod - b.v); }
	   inline modint& operator*=(const modint b) { v = v * b.v % mod; return *this; }
	   inline modint& operator/=(const modint b) { v = v * b.inv().v % mod; return *this; }
	   inline modint operator+(const modint& b) const { return modint(v) += b; }
	   inline modint operator-(const modint& b) const { return modint(v) -= b; }
	   inline modint operator*(const modint& b) const { return modint(v) *= b; }
	   inline modint operator/(const modint& b) const { return modint(v) /= b; }
	   friend ostream& operator<<(ostream& os, const modint& m) {
		   return os << m.v;
	   }
	   friend istream& operator>>(istream& is, modint& m) {
		   int x; is >> x; m = modint(x);
		   return is;
	   }
	   bool operator<(const modint& r)const { return v < r.v; }
	   bool operator>(const modint& r)const { return v > r.v; }
	   bool operator<=(const modint& r)const { return v <= r.v; }
	   bool operator>=(const modint& r)const { return v >= r.v; }
	   bool operator==(const modint& r)const { return v == r.v; }
	   bool operator!=(const modint& r)const { return v != r.v; }
	   explicit operator bool()const { return v; }
	   explicit operator int()const { return v; }
	   modint comb(modint k) {
		   if (k > *this) return modint();
		   if (fact.empty()) combinit();
		   if (v >= fn_) {
			   if (k > *this - k) k = *this - k;
			   modint tmp(1);
			   for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
			   return tmp * comp[k.v];
		   }
		   return fact[v] * comp[k.v] * comp[v - k.v];
	   }//nCk
	   modint perm(modint k) {
		   if (k > *this) return modint();
		   if (fact.empty()) combinit();
		   if (v >= fn_) {
			   modint tmp(1);
			   for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
			   return tmp;
		   }
		   return fact[v] * comp[v - k.v];
	   }//nPk
	   static void combinit() {
		   fact.assign(fn_, modint());
		   fact[0] = 1;
		   for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * modint(i);
		   comp.assign(fn_, modint());
		   comp[fn_ - 1] = fact[fn_ - 1].inv();
		   for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * modint(i + 1);
	   }
};
using mint = modint<ll(1e9 + 7)>; template<>vec<mint> mint::fact = vec<mint>(); template<>vec<mint> mint::comp = vec<mint>();
//--------------------------------------------------------------
class unionfind {
	int size = 0, grps = 0;
	vector<int>pa;
public:
	unionfind() {}
	unionfind(int n) {
		init(n);
	}
	void init(int n) {
		size = n, grps = n;
		pa.assign(n + 1, -1);
	}
	int root(int x) {
		if (pa[x] < 0) return x;
		return pa[x] = root(pa[x]);
	}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		grps--;
		if (pa[x] > pa[y]) swap(x, y);
		pa[x] += pa[y];
		pa[y] = x;
		return true;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	bool isroot(int x) {
		return x == root(x);
	}
	int sz(int x) {
		return -pa[root(x)];
	}
	int groups() {
		return grps;
	}
	H operator[](int x) {
		x = root(x);
		return H{ x,-pa[x] };
	}
};
//--------------------------------------------------------------
struct A {
	int a, b;
};
int n, m, q;
vec<int>e[200000];
vec<A>edg;
int dp[200000];
int sz[200000];
int in[200000], idx;
int out[200000];
int head[200000];
int dpt[200000], par[200000];
void dfs_sz(int v, int p, int d) {
	sz[v] = 1;
	par[v] = p;
	dpt[v] = d;
	if (e[v][0] == p) swap(e[v][0], e[v].back());
	for (auto& g : e[v]) {
		if (g == p) continue;
		dfs_sz(g, v, d + 1);
		sz[v] += sz[g];
		if (sz[g]>sz[e[v][0]]) swap(g, e[v][0]);
	}
}
void dfs_hld(int v, int p) {
	out[idx] = v;
	in[v] = idx++;
	for (auto g : e[v]) {
		if (g == p) continue;
		head[g] = (g == e[v][0] ? head[v] : g);
		dfs_hld(g, v);
	}
}
int dat[200000];
void add(int x, int v) {
	x++;
	while (x <= idx) {
		dat[x] += v;
		x += x&-x;
	}
}
int sum1(int x) {
	x++;
	int sum = 0;
	while (x>0) {
		sum += dat[x];
		x -= x&-x;
	}
	return sum;
}
int sum(int l, int r) {
	return sum1(r - 1) - sum1(l - 1);
}
int lb(int l, int r) {
	int ok = l, ng = r, mid;
	while (ng - ok>1) {
		mid = (ok + ng) / 2;
		if (sum(mid, r)>0) ok = mid;
		else ng = mid;
	}
	return ok;
}
void add_hld(int l, int r, int x) {
	if (dpt[l]>dpt[r]) swap(l, r);
	add(in[r], x);
}
int fst_hld(int x) {
	while (head[x] != 0) {
		if (sum(in[head[x]], in[x] + 1)>0) {
			return out[lb(in[head[x]], in[x] + 1)];
		}
		x = par[head[x]];
	}
	if (sum(in[head[x]], in[x] + 1)>0) {
		return out[lb(in[head[x]], in[x] + 1)];
	}
	return 0;
}//さかのぼっていく途中で、初めて値がついている辺はどこだ？
signed main() {
	cin >> n >> m >> q;
	rep(i, n - 1) {
		int u, v; cin >> u >> v;
		u--; v--;
		e[u].pb(v);
		e[v].pb(u);
		edg.pb(A{ u,v });
	}

	dfs_sz(0, -1, 0); dfs_hld(0, -1);
	rep(i, n - 1) {
		if (dpt[edg[i].a]>dpt[edg[i].b]) {
			swap(edg[i].a, edg[i].b);
		}
	}
	for (auto g : edg) {
		add_hld(g.a, g.b, 1);
	}
	vec<bool>b(n, 0);
	vec<int>c(n, 0);
	rep(i, n) dp[i] = 1;
	rep(i, m) {
		int d; cin >> d;
		d--;
		b[d] = !b[d];
		if (b[d]) {
			int t = fst_hld(par[edg[d].b]);
			dp[t] += dp[edg[d].b] - c[edg[d].b];
			add_hld(edg[d].a, edg[d].b, -1);
		}
		else {
			int t = fst_hld(edg[d].b);
			dp[edg[d].b] = dp[t];
			c[edg[d].b] = dp[edg[d].b];
			add_hld(edg[d].a, edg[d].b, 1);
		}
	}
	rep(i, q) {
		int v; cin >> v;
		v--;
		cout << dp[fst_hld(v)] << endl;
	}
}

Compilation message

synchronization.cpp: In function 'll read()':
synchronization.cpp:69:19: warning: unused variable 'k' [-Wunused-variable]
   69 | ll read() { ll u, k = scanf("%lld", &u); return u; }
      |                   ^
synchronization.cpp: In function 'H readh(short int)':
synchronization.cpp:71:33: warning: unused variable 'k' [-Wunused-variable]
   71 | H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
      |                                 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 20 ms 5996 KB Output is correct
8 Correct 20 ms 5996 KB Output is correct
9 Correct 20 ms 5996 KB Output is correct
10 Correct 256 ms 15072 KB Output is correct
11 Correct 254 ms 14944 KB Output is correct
12 Correct 285 ms 24288 KB Output is correct
13 Correct 155 ms 14808 KB Output is correct
14 Correct 193 ms 14432 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 19424 KB Output is correct
2 Correct 146 ms 19296 KB Output is correct
3 Correct 169 ms 23648 KB Output is correct
4 Correct 168 ms 23648 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 11 ms 5228 KB Output is correct
7 Correct 52 ms 7020 KB Output is correct
8 Correct 592 ms 25056 KB Output is correct
9 Correct 584 ms 25184 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 585 ms 25056 KB Output is correct
2 Correct 478 ms 24672 KB Output is correct
3 Correct 470 ms 24800 KB Output is correct
4 Correct 485 ms 24928 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 8 ms 5100 KB Output is correct
6 Correct 48 ms 6124 KB Output is correct
7 Correct 539 ms 15968 KB Output is correct
8 Correct 588 ms 25184 KB Output is correct
9 Correct 422 ms 16344 KB Output is correct
10 Correct 480 ms 15868 KB Output is correct
11 Correct 411 ms 20668 KB Output is correct
12 Correct 409 ms 20576 KB Output is correct
13 Correct 480 ms 24808 KB Output is correct