Submission #1102484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102484	2024-10-18T07:58:03 Z	vjudge1	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	1491 ms	207264 KB

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

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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	49488 KB	Output is correct
2	Correct	20 ms	51404 KB	Output is correct
3	Correct	100 ms	71608 KB	Output is correct
4	Correct	769 ms	207264 KB	Output is correct
5	Correct	1037 ms	207008 KB	Output is correct
6	Correct	1219 ms	207196 KB	Output is correct
7	Correct	339 ms	91804 KB	Output is correct

Subtask #2

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	49744 KB	Output is correct
2	Correct	16 ms	49912 KB	Output is correct
3	Correct	14 ms	49744 KB	Output is correct
4	Correct	18 ms	49960 KB	Output is correct
5	Correct	16 ms	49744 KB	Output is correct
6	Correct	20 ms	49744 KB	Output is correct
7	Correct	14 ms	49744 KB	Output is correct
8	Correct	15 ms	49744 KB	Output is correct
9	Correct	14 ms	50000 KB	Output is correct
10	Correct	17 ms	50000 KB	Output is correct
11	Correct	18 ms	50000 KB	Output is correct
12	Correct	16 ms	50012 KB	Output is correct
13	Correct	14 ms	50000 KB	Output is correct
14	Correct	14 ms	49912 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	50512 KB	Output is correct
2	Correct	35 ms	56648 KB	Output is correct
3	Correct	87 ms	64328 KB	Output is correct
4	Correct	50 ms	60916 KB	Output is correct
5	Correct	612 ms	124488 KB	Output is correct
6	Correct	729 ms	122952 KB	Output is correct
7	Correct	671 ms	122184 KB	Output is correct
8	Correct	706 ms	127612 KB	Output is correct
9	Correct	719 ms	149320 KB	Output is correct
10	Correct	798 ms	156960 KB	Output is correct
11	Correct	395 ms	181064 KB	Output is correct
12	Correct	387 ms	181012 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	49488 KB	Output is correct
2	Correct	20 ms	51404 KB	Output is correct
3	Correct	100 ms	71608 KB	Output is correct
4	Correct	769 ms	207264 KB	Output is correct
5	Correct	1037 ms	207008 KB	Output is correct
6	Correct	1219 ms	207196 KB	Output is correct
7	Correct	339 ms	91804 KB	Output is correct
8	Correct	16 ms	49744 KB	Output is correct
9	Correct	16 ms	49912 KB	Output is correct
10	Correct	14 ms	49744 KB	Output is correct
11	Correct	18 ms	49960 KB	Output is correct
12	Correct	16 ms	49744 KB	Output is correct
13	Correct	20 ms	49744 KB	Output is correct
14	Correct	14 ms	49744 KB	Output is correct
15	Correct	15 ms	49744 KB	Output is correct
16	Correct	14 ms	50000 KB	Output is correct
17	Correct	17 ms	50000 KB	Output is correct
18	Correct	18 ms	50000 KB	Output is correct
19	Correct	16 ms	50012 KB	Output is correct
20	Correct	14 ms	50000 KB	Output is correct
21	Correct	14 ms	49912 KB	Output is correct
22	Correct	23 ms	50512 KB	Output is correct
23	Correct	35 ms	56648 KB	Output is correct
24	Correct	87 ms	64328 KB	Output is correct
25	Correct	50 ms	60916 KB	Output is correct
26	Correct	612 ms	124488 KB	Output is correct
27	Correct	729 ms	122952 KB	Output is correct
28	Correct	671 ms	122184 KB	Output is correct
29	Correct	706 ms	127612 KB	Output is correct
30	Correct	719 ms	149320 KB	Output is correct
31	Correct	798 ms	156960 KB	Output is correct
32	Correct	395 ms	181064 KB	Output is correct
33	Correct	387 ms	181012 KB	Output is correct
34	Correct	255 ms	75424 KB	Output is correct
35	Correct	337 ms	82204 KB	Output is correct
36	Correct	449 ms	90300 KB	Output is correct
37	Correct	1077 ms	150432 KB	Output is correct
38	Correct	1202 ms	149072 KB	Output is correct
39	Correct	1276 ms	148496 KB	Output is correct
40	Correct	1409 ms	152736 KB	Output is correct
41	Correct	1491 ms	177684 KB	Output is correct
42	Correct	1420 ms	207136 KB	Output is correct
43	Correct	952 ms	206752 KB	Output is correct
44	Correct	950 ms	206752 KB	Output is correct
45	Correct	1204 ms	178372 KB	Output is correct
46	Correct	13 ms	49488 KB	Output is correct