Submission #1102462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102462		flyingkite	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	1519 ms	354936 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n,q,m = 0;
vector<ll>adj[N], row[N], g[N], pos[N];
vector<pll>t[N];
ll idx[N], ps[N], res[N];
vector<ll>topo;
void dfs(ll u, ll par){
    m = max(m, idx[u]);
    ll pos = -1;
    for(int i = 0; i < adj[u].size();i++) if(adj[u][i] == par) pos = i;
    for(int i = 0; i < adj[u].size();i++){
        ll v = adj[u][i];
        if(i < pos) idx[v] = idx[u];
        else if(i > pos) idx[v] = idx[u] + 1;
    }
    for(auto v : adj[u]) if(v != par) dfs(v, u);
    for(int i = pos + 1; i < adj[u].size();i++) g[u].pb(adj[u][i]);
    for(int i = 0; i < pos;i++) g[u].pb(adj[u][i]);
}
void dfs_topo(ll u){
    for(auto v : g[u]) {
        topo.pb(v);
        row[idx[v]].pb((ll)topo.size() - 1);
        dfs_topo(v);
        topo.pb(u);
        row[idx[v]].pb((ll)topo.size() - 1);
    }
}
struct fenwick_tree{
	ll n;
	vector<ll>ft;
	void init(ll _n){
		n = _n;
		ft.resize(n + 10);
	}
	void update(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;
	}
} ft;
void to_thic_cau(){
    cin >> n >> q;
    for(int i = 1; i <= n;i++){
        ll k; cin >> k;
        vector<ll>tmp;
        for(int j = 1; j <= k;j++){
            ll x; cin >> x;
            tmp.pb(x);
        }
        for(int j = 1; j < tmp.size();j++) adj[i].pb(tmp[j]);
        adj[i].pb(tmp[0]);
    }
    idx[1] = 1;     
    topo.pb(0);
    dfs(1, 0); 

    dfs_topo(1);
    ll tot = 0;
    for(int i = 1; i <= m;i++){
        tot += (ll)row[i].size();
        ps[i] = ps[i-1] + tot;
    }
    for(int i = 1; i <= q;i++){
        ll k; cin >> k;
        ll j = lower_bound(ps + 1, ps + m + 1, k) - ps;
        if(j > m){
            res[i] = topo[(k - ps[m] - 1) % ((ll)topo.size() - 1) + 1];
        }
        else t[j].pb({k - ps[j-1], i});
    }
    ft.init((ll)topo.size());
    for(int i = 1; i <= m;i++){
        for(auto x : row[i]) ft.update(x, 1);
        for(auto x : t[i]){
            ll val = x.F, idx = x.S;
            ll l = 1, r = (ll)topo.size() - 1, pos = -1;
            while(l <= r){
                ll mid = (l + r) / 2;
                if(ft.get(mid) >= val) pos = mid, r = mid - 1;
                else l = mid + 1;
            }
            res[idx] = topo[pos];
        }
    }
    for(int i = 1; i <= q;i++) cout << res[i] << "\n";
}   

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < adj[u].size();i++) if(adj[u][i] == par) pos = i;
      |                    ~~^~~~~~~~~~~~~~~
Main.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < adj[u].size();i++){
      |                    ~~^~~~~~~~~~~~~~~
Main.cpp:30:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = pos + 1; i < adj[u].size();i++) g[u].pb(adj[u][i]);
      |                          ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void to_thic_cau()':
Main.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j = 1; j < tmp.size();j++) adj[i].pb(tmp[j]);
      |                        ~~^~~~~~~~~~~~

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