제출 #333921

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

synchronization

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

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

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