oj.uz

Submission #428026

# Submission time Handle Problem Language Result Execution time Memory
428026 2021-06-15T07:22:50 Z codebuster_10 Synchronization (JOI13_synchronization) C++17
100 / 100
 1014 ms 35480 KB 
#include <bits/stdc++.h>

using namespace std ;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}





template <class T, int ...Ns> struct BIT {
	T val = 0; void upd(T v) { val += v; }
	T query() { return val; }
};
template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T,Ns...> bit[N+1];
	template<typename... Args> void upd(int pos, Args... args) { assert(pos > 0);
		for (; pos<=N; pos+=pos&-pos) bit[pos].upd(args...); }
	template<typename... Args> T sum(int r, Args... args) {
		T res=0; for (;r;r-=r&-r) res += bit[r].query(args...); 
		return res; }
	template<typename... Args> T query(int l, int r, Args... 
		args) { return sum(r,args...)-sum(l-1,args...); }
}; 



const int MAX_N = 1e5 + 7, LOG = 20;
BIT<int,MAX_N> bit;
vector<int> g[MAX_N];
int st[MAX_N], en[MAX_N], up[MAX_N][LOG], timer, ans[MAX_N], edge[MAX_N], active[MAX_N];


void dfs(int i,int p){
  st[i] = timer++;
  up[i][0] = p;
  for(int j = 1; j < LOG; ++j){
    up[i][j] = up[up[i][j-1]][j-1];
  } 
  for(auto j : g[i]) if(j != p) {
    dfs(j,i);
  }
  en[i] = timer - 1 ;
}


signed main(){
	int n,m,q; rd(n,m,q);
	vt<ar<int,2>> edges;
	f(_,0,n-1){
		int u,v; rd(u,v); --u,--v;
		edges.pb({u,v});
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(0,0);
	
	fill(ans, ans + n, 1);
	fill(edge, edge + n, 0);
	fill(active, active + n, 0);
	
	for(auto& [u,v] : edges){
		if(st[v] > st[u]) swap(u,v);
	}
	
	auto add = [&](int x,int v) -> void {
		// add value in edge whose lower node is x.
		bit.upd(st[x],v);
		bit.upd(en[x]+1,-v);
		return;
	};
	
	auto get = [&](int x) -> int {
		// get sum of edges whose lower node is x.
		if(x == 0) return int(0);
		return bit.query(1,st[x]);
	};
	
	auto root = [&](int x) -> int {
		for(int i = LOG - 1; i >= 0; --i){
			int j = up[x][i];
			if(get(x) - get(j) == (1<<i)){
				x = j;
			}
		}
		return x;
	};
	

	f(_,0,m){
		int d; rd(d); --d;
		auto [u,v] = edges[d];// here u is child and v is parent.
		if(active[d]){
			assert(root(u) == root(v));
			edge[u] = ans[u] = ans[root(v)];
			add(u,-1);
		}else{
			int tmp = ans[root(u)] + ans[root(v)] - edge[u];
			edge[u] = tmp;
			add(u,1);
			assert(root(u) == root(v));
			ans[root(v)] = tmp;
		}
		active[d] ^= 1;
	}
	
	while(q--){
		int c; rd(c); --c;
		cout << ans[root(c)] << endl;
	}
	
}

Compilation message

synchronization.cpp: In function 'void setIO(std::string)':
synchronization.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:85:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2656 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 43 ms 5364 KB Output is correct
8 Correct 45 ms 5448 KB Output is correct
9 Correct 44 ms 5448 KB Output is correct
10 Correct 620 ms 30588 KB Output is correct
11 Correct 603 ms 30600 KB Output is correct
12 Correct 693 ms 34680 KB Output is correct
13 Correct 336 ms 30404 KB Output is correct
14 Correct 456 ms 30104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 32432 KB Output is correct
2 Correct 329 ms 32204 KB Output is correct
3 Correct 376 ms 34116 KB Output is correct
4 Correct 405 ms 33996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 4 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 8 ms 2920 KB Output is correct
7 Correct 68 ms 5916 KB Output is correct
8 Correct 955 ms 35452 KB Output is correct
9 Correct 951 ms 35440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 35444 KB Output is correct
2 Correct 634 ms 34996 KB Output is correct
3 Correct 715 ms 35272 KB Output is correct
4 Correct 736 ms 35172 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 8 ms 2904 KB Output is correct
6 Correct 64 ms 5492 KB Output is correct
7 Correct 919 ms 31408 KB Output is correct
8 Correct 1014 ms 35480 KB Output is correct
9 Correct 598 ms 31412 KB Output is correct
10 Correct 670 ms 31372 KB Output is correct
11 Correct 653 ms 33564 KB Output is correct
12 Correct 578 ms 33608 KB Output is correct
13 Correct 663 ms 35248 KB Output is correct