Submission #1102484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102484		vjudge1	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	1491 ms	207264 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2")
#include<bits/stdc++.h>
#define pll pair<long long, long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
#define lowbit(x) (x & (-x))
#define sigma main
using namespace std;
 
const long long inf = 1e18; 
const int mod = 1e9+7;
const int MAXN = 2e6+100;
 
#define int long long
 
struct fenwick_tree{
	#define ll long long
	ll n;
    vector<ll>ft;
    void init(ll _n){
        n = _n;
        ft.resize(n + 10);
    }
    void add(ll idx, ll val){
        while(idx <= n) ft[idx] = (ft[idx] + val), idx += (idx & (-idx));
    }
    ll get(ll idx){
        ll res = 0;
        while(idx > 0) res = (res + ft[idx]), idx -= (idx & (-idx));
        return res;
    }
    ll get(ll l, ll r){return get(r) - get(l - 1);} 
} T , S;
 
pll order[MAXN];
vector<int> adj[MAXN];
int Time = 0 , par[MAXN];
 
void dfs(int u , int p){
	int pos = -1;
	for(int i = 0 ; i < adj[u].size() ; i++){
		int v = adj[u][i];
		if(v == p) pos = i;
	}

	for(int i = pos + 1 ; i < adj[u].size() ; i++){
		int v = adj[u][i];
		order[v].fi = ++Time;
		par[v] = u;
		dfs(v , u);
		order[v].se = ++Time;
	}

	for(int i = 0 ; i < pos ; i++){
		int v = adj[u][i];
		order[v].fi = ++Time;
		par[v] = u;
		dfs(v , u);
		order[v].se = ++Time;
	}
 
}
int32_t sigma(){
  	//freopen("MILITARYTRAINING.inp", "r", stdin);
	//freopen("MILITARYTRAINING.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n , q; cin >> n >> q;
	for(int i = 1 ; i <= n ; i++){
		int k; cin >> k;
		while(k--){
			int x; cin >> x;
			adj[i].push_back(x);
		}
	}
 
	for(int i = 1 ; i <= n ; i++){
		reverse(adj[i].begin() , adj[i].end());
		int t = adj[i].back();
		adj[i].pop_back();
		reverse(adj[i].begin() , adj[i].end());
		adj[i].push_back(t);
	}
 
	dfs(1 , 1);
	
	vector<pll> query;
	vector<int> ans(q + 1);
	for(int i = 1 ; i <= q; i ++){
		int x; cin >> x;
		query.push_back({x , i});
	}
	sort(query.begin() , query.end());
	deque<pll> Q;
 
	assert(Time == (n-1)*2);
	T.init(Time+10) , S.init(Time+10);
	Q.push_back({1 , 0});
	int jj = 0;
	int state = 0 , tl = 0 , cnt = 0;
	while(Q.size()){
		pll t = Q.front(); Q.pop_front();
		int u = t.fi , st = t.se;
		
		if(st > state){
			for(; jj < query.size() && query[jj].fi <= tl + cnt * 2 ; jj++){
				pll X = query[jj];
 
				int res = -1;
				int l = 1 , r = Time;
				while(l <= r){
					int mid = l + r >> 1;
					if(S.get(1 , mid) >= X.fi - tl){
						res = mid ; r = mid-1;
					}else{
						l = mid+1;
					}
				}
				ans[X.se] = T.get(res , res);
				
			}
			tl += cnt * 2;
			state++;
		}
		
		if(u != 1){
			cnt++;
			T.add(order[u].fi , u);
			S.add(order[u].fi , 1);
			T.add(order[u].se , par[u]);
			S.add(order[u].se , 1);
		}
		vector<int> nxt;
		int K = 0;
		for(auto v : adj[u]){
			if(v == par[u]) K++;
			else{
				if(K == 0) nxt.push_back(v);
				else Q.push_back({v , st + 1});
			}
		}
 
		while(nxt.size() > 0){
			Q.push_front({nxt.back() , st}); nxt.pop_back();
		}
 
	}
	
	for(; jj < query.size() ; jj++){
		pll &X = query[jj];
	
		X.fi -= tl;
		X.fi %= cnt * 2;
		if(X.fi == 0) X.fi = cnt * 2;
		int res = -1;
		int l = 1 , r = Time;
		while(l <= r){
			int mid = l + r >> 1;
			if(S.get(1 , mid) >= X.fi){
				res = mid ; r = mid-1;
			}else{
				l = mid+1;
			}
		}
		ans[X.se] = T.get(res , res);		
	}
 
	for(int i = 1 ; i <= q ; i++) cout << ans[i] << "\n";
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:43:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0 ; i < adj[u].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp:48:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = pos + 1 ; i < adj[u].size() ; i++){
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:108:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(; jj < query.size() && query[jj].fi <= tl + cnt * 2 ; jj++){
      |          ~~~^~~~~~~~~~~~~~
Main.cpp:114:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |      int mid = l + r >> 1;
      |                ~~^~~
Main.cpp:151:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for(; jj < query.size() ; jj++){
      |        ~~~^~~~~~~~~~~~~~
Main.cpp:160:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |    int mid = l + r >> 1;
      |              ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 12 / 12
• Subtask 4: 5 / 5