제출 #333921

#제출 시각아이디문제언어결과실행 시간메모리
333921Thistle동기화 (JOI13_synchronization)C++14
100 / 100
592 ms25184 KiB
#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; }
      |                                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...