oj.uz

Submission #428401

# Submission time Handle Problem Language Result Execution time Memory
428401 2021-06-15T11:23:34 Z codebuster_10 Synchronization (JOI13_synchronization) C++17
100 / 100
 864 ms 35488 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]){
			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);
			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 2 ms 2656 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 35 ms 5352 KB Output is correct
8 Correct 33 ms 5448 KB Output is correct
9 Correct 33 ms 5448 KB Output is correct
10 Correct 486 ms 30480 KB Output is correct
11 Correct 513 ms 30580 KB Output is correct
12 Correct 559 ms 34744 KB Output is correct
13 Correct 263 ms 30304 KB Output is correct
14 Correct 372 ms 30064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 32444 KB Output is correct
2 Correct 286 ms 32024 KB Output is correct
3 Correct 317 ms 34168 KB Output is correct
4 Correct 352 ms 34032 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 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 7 ms 2892 KB Output is correct
7 Correct 66 ms 5920 KB Output is correct
8 Correct 836 ms 35436 KB Output is correct
9 Correct 864 ms 35424 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 35376 KB Output is correct
2 Correct 593 ms 35084 KB Output is correct
3 Correct 598 ms 35204 KB Output is correct
4 Correct 600 ms 35284 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 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2720 KB Output is correct
5 Correct 7 ms 2892 KB Output is correct
6 Correct 56 ms 5504 KB Output is correct
7 Correct 750 ms 31404 KB Output is correct
8 Correct 800 ms 35488 KB Output is correct
9 Correct 526 ms 31400 KB Output is correct
10 Correct 634 ms 31236 KB Output is correct
11 Correct 557 ms 33620 KB Output is correct
12 Correct 595 ms 33528 KB Output is correct
13 Correct 609 ms 35232 KB Output is correct