제출 #1292246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292246		Minbaev	Synchronization (JOI13_synchronization)	C++20	30 / 100	211 ms	24464 KiB

synchronization

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
// #define double  long double
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

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

int binpow(int a, int b, int m){
    if(b <= 0)return 1; 	
    if(b % 2 == 0){
        int c = binpow(a,b/2,m);
        return (c*c)%m;
    }
    return (binpow(a,b-1,m)*a)%m;
}

int divi(int a, int b, int m){
    return (a*(binpow(b,m-2, m)))%m;
}

struct modint {
    static int mod;
    long long val;

    modint(long long v = 0) {
        val = v % mod;
        if (val < 0) val += mod;
    }

    modint& operator+=(const modint& other) {
        val += other.val;
        if (val >= mod) val -= mod;
        return *this;
    }
    modint& operator+=(long long other) {
        return *this += modint(other);
    }

    modint& operator-=(const modint& other) {
        val -= other.val;
        if (val < 0) val += mod;
        return *this;
    }
    modint& operator-=(long long other) {
        return *this -= modint(other);
    }

    modint& operator*=(const modint& other) {
        val = (val * other.val) % mod;
        return *this;
    }
    modint& operator*=(long long other) {
        return *this *= modint(other);
    }

    modint& operator/=(const modint& other) {
        val = divi(val, other.val, mod);
        return *this;
    }
    modint& operator/=(long long other) {
        return *this /= modint(other);
    }

    friend modint operator+(modint a, const modint& b) { return a += b; }
    friend modint operator+(modint a, long long b) { return a += b; }
    friend modint operator+(long long a, modint b) { return b += a; }

    friend modint operator-(modint a, const modint& b) { return a -= b; }
    friend modint operator-(modint a, long long b) { return a -= b; }
    friend modint operator-(long long a, modint b) { return modint(a) -= b; }

    friend modint operator*(modint a, const modint& b) { return a *= b; }
    friend modint operator*(modint a, long long b) { return a *= b; }
    friend modint operator*(long long a, modint b) { return b *= a; }

    friend modint operator/(modint a, const modint& b) { return a /= b; }
    friend modint operator/(modint a, long long b) { return a /= b; }
    friend modint operator/(long long a, modint b) { return modint(a) /= b; }

    friend ostream& operator<<(ostream& os, const modint& m) {
        return os << m.val;
    }
};

int modint::mod = 1e9 + 7;

namespace FAST {
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 3e18 + 7;
const int mod = 1e9 + 7;
const int N = 6e5 + 5;
const int md = 998244353;

int rev(int a, int m){
	if (a == 1)return 1;
	return (1 - rev(m % a, a) * m) / a + m;
}

struct Bit {
    vector<int> b, b2;
    int n;

    Bit(int n) {
        this->n = n + 1;
        b.assign(n + 1, 0);
        b2.assign(n+1, 0);
    }

    void add(vector<int>&b, int idx, int x){
        while(idx <= n){
            b[idx] += x;
            idx += idx & -idx;
        }
    }

    void upd(int l, int r, int x){
        add(b, l, x);
        add(b, r+1, -x);
        add(b2, l, x*(l-1));
        add(b2, r+1, -x*r);
    }

    int sum(vector<int>&b, int idx){
        int res = 0;
        while(idx > 0){
            res += b[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    int pref(int idx){
        return sum(b, idx) * idx - sum(b2, idx);
    }

    int get(int l, int r){                  
        return pref(r) - pref(l-1);
    }
};

int n,m,k;
vector<int>g[N], ans[N];

struct Tree{
	int sz;
	vector<int>t, bn;
	Tree(int n){
		this->sz = n;
		t.resize(sz * 4 + 5);
		bn.resize(sz * 4 + 5);
	}
	
	void push(int tl, int tr, int v){
		if(bn[v] == 0)return;
		if(tl < tr){
			bn[v*2] = bn[v];
			bn[v*2+1] = bn[v];
		}
		t[v] = bn[v];
		bn[v] = 0;
	}
	
	void update(int tl, int tr, int v, int l, int r, int val){
		if(r < l || tr < l || r < tl)return;
		push(tl, tr, v);
		if(l <= tl && tr <= r){
			bn[v] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		update(tl, tm, v*2, l, r, val);
		update(tm+1, tr, v*2+1, l, r, val);
	}
	
	void upd(int l, int r, int x){
		update(1, sz, 1, l, r, x);
	}
	
	int gt(int tl, int tr, int v, int pos){
		push(tl, tr, v);
		if(tl == tr){
			return t[v];
		}
		int tm = (tl + tr) / 2;
		
		if(pos <= tm)
			return gt(tl, tm, v*2, pos);
		else return gt(tm+1, tr, v*2+1, pos);
	}
	
	int get(int pos){
		return gt(1, sz, 1, pos);
	}	
};

void solve(){
	
	cin >> n >> m >> k;
	
	vector<ar<int,2>>vs;
	vs.pb({1, 1});
	
	for(int i = 2;i<=n;i++){
		int a,b;
		cin >> a >> b;
		if(a > b)swap(a, b);
		g[a].pb(b);
		g[b].pb(a);
		vs.pb({a, b});
	}
	
	Bit res(n + 5);
	Tree l(n + 5), r(n + 5);
	vector<ar<int,2>>t(n + 5, {1, 1});
	
	for(int i = 1;i<=n;i++){
		l.upd(i, i, i);
		r.upd(i, i, i);
		res.upd(i, i, 1);
	}
	
	vector<int>cnt(n + 5);
	
	//~ return;
	
	for(int i = 1;i<=m;i++){
		int a;
		cin >> a;
		
		if(cnt[a] % 2 == 0){
			int u,v;
			u = vs[a][0];
			v = vs[a][1];
			
			int l1 = l.get(u);
			int r1 = r.get(v);
			
			int val = t[u][1];
			int h = t[v][0];
			
			if(val > 0){
				res.upd(v, r1, val);
				t[r1][1] += val;
			}
			
			if(h > 0){
				res.upd(l1, u, h);
				t[l1][0] += h;
			}
			
			
			t[u][1] = 0;
			t[v][0] = 0;
			
			l.upd(l1, r1, l1);
			r.upd(l1, r1, r1);
		}
		//--------
		else{
			int u,v;
			u = vs[a][0];
			v = vs[a][1];
			
			int l1 = l.get(u);
			int r1 = r.get(v);
			
			l.upd(v, r1, v);
			r.upd(l1, u, u);
		}
		
		cnt[a] += 1;
	}
	
	for(int i = 1;i<=k;i++){
		int a;
		cin >> a;
		cout << res.get(a, a) << "\n";
		//~ cout << t[a] << " " << l.get(a) << " " << r.get(a) << "\n";
	}
	
	
	
	
}
/*
9 10 9 
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

2 
3 
5 
6 
4 
4 
1 
7 
8 
4 

1
2
3
4
5
6
7
8
9
*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;//cin >> tt;
    while(tt--)solve();	

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40