Submission #1189377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189377		overfit	Through Another Maze Darkly (CCO21_day1problem3)	C++20	25 / 25	2771 ms	641908 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)

using namespace std;
typedef long long ll;
const int maxn = 800005;

struct Node{
    int ls, rs;
    int cnt;
}tr[(maxn * 2) * (4 + 20)];
int root[maxn << 1], idx;
vector<int> to[maxn], pos[maxn], ne;
int n, Q, m;
int seq[maxn << 1], len;
int fa[maxn], ind[maxn];
int now[maxn], tot;
ll sum[maxn];
queue<int> q;

int build(int l, int r){
    int p = ++ idx;
    if (l == r){
        return p;
    }
    tr[p].ls = build(l, mid), tr[p].rs = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x){
    int q = ++ idx;
    tr[q] = tr[p];
    if (l == r){
        tr[q].cnt = 1;
        return q;
    }
    if (x <= mid) tr[q].ls = insert(tr[p].ls, l, mid, x);
    else tr[q].rs = insert(tr[p].rs, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].ls].cnt + tr[tr[q].rs].cnt;
    return q;
}

int query(int p, int l, int r, int k){//Kth problem
    if (l == r){
        return l;
    }
    int cnt = tr[tr[p].ls].cnt;
    if (cnt >= k) return query(tr[p].ls, l, mid, k);
    else return query(tr[p].rs, mid + 1, r, k - cnt);
}

void init(int u, int _fa){
    fa[u] = _fa;
    for (int i = 0; i < to[u].size(); i ++){
        int v = to[u][i];
        if (v == fa[u]){
            ind[u] = i;
            continue;
        }
        init(v, u);
    }
}

void get(int u){
    if (u > 1) seq[++ len] = u, pos[u].push_back(len);
    int i = ind[u];
    while (true){
        i ++, i %= to[u].size();
        int v = to[u][i];
        if (i == ind[u] && u > 1) break;
        get(v);
        seq[++ len] = u, pos[u].push_back(len);
        if (i == ind[u] && u == 1) break;
    }
}

void dfs(int u, int t){
    now[u] ++, now[u] %= to[u].size();
    if (u != t){
        root[m] = insert(root[m], 1, len, *pos[u].rbegin());
        pos[u].pop_back();
    }
    if (now[u] == ind[u] && u != t){
        ne.push_back(u);
        return;
    }
    int i = now[u] - 1;
    int back_up = now[u];
    while (true){
        i ++, i %= to[u].size(), now[u] = i;
        int v = to[u][i];
        if (i == ind[u] && u > 1) break;
        dfs(v, t);
        root[m] = insert(root[m], 1, len, *pos[u].rbegin());
        pos[u].pop_back();
        if (i == ind[u] && u == 1) break;
    }
    ind[u] = back_up;

    if (!pos[u].empty()) ne.push_back(u);
    return;
}

void file(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#define task "MAZE"
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
}

int32_t main() {
    file();

    cin >> n >> Q;
    for (int u = 1, k, v; u <= n; u ++){
        cin >> k;
        while (k --){
            cin >> v;
            to[u].push_back(v);
        }
    }

    init(1, 0), get(1);
    q.push(1), root[0] = build(1, len);
    while (!q.empty()){
        m ++, root[m] = root[m - 1];

        while (!q.empty()){
            int u = q.front();
            q.pop();
            dfs(u, u);
        }
        for (vector<int>::iterator it = ne.begin(); it != ne.end(); it ++){
            q.push(*it);
        }
        ne.clear();
        sum[m] = sum[m - 1] + tr[root[m]].cnt;
        if (tr[root[m]].cnt == len) break;
    }

    ll k;
    while (Q --){
        cin >> k;
        int t = lower_bound(sum + 1, sum + m + 1, k) - sum;
        k -= sum[t - 1];
        if (t < m){
            cout << seq[query(root[t], 1, len, k)] << endl;
        }
        else{
            k %= len;
            if (k == 0) k = len;
            cout << seq[k] << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void file()':
Main.cpp:110:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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