Submission #698631

#	Time	Username	Problem	Language	Result	Execution time	Memory
698631		azberjibiou	Through Another Maze Darkly (CCO21_day1problem3)	C++17	25 / 25	1287 ms	228744 KiB

Main

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
typedef long long ll;
using namespace std;
const int mxN=800005;
struct fenwick{
    int siz;
    int fen[2*mxN];
    void upd(int idx, int val){while(idx<=siz) fen[idx]+=val, idx+=(idx&(-idx));}
    int sum(int idx)
    {
        int ret=0;
        while(idx)  ret+=fen[idx], idx-=(idx&(-idx));
        return ret;
    }
    int solv(int s, int e){return sum(e)-sum(s-1);}
};
ll N, Q;
vector <int> E[mxN], chd[mxN];
int par[mxN];
vector <int> ETT;
int M;
int in[mxN], out[mxN], dir[2*mxN];
fenwick F;
vector <pll> qry;
int ans[mxN];
void dfs1(int now, int pre)
{
    for(int nxt : E[now])   if(nxt!=pre)
    {
        par[nxt]=now;
        dfs1(nxt, now);
    }
}
void dfs2(int now)
{
    for(int nxt : chd[now])
    {
        ETT.push_back(nxt);
        in[nxt]=(int)ETT.size()-1;
        dfs2(nxt);
        ETT.push_back(now);
        out[nxt]=(int)ETT.size()-1;
    }
}
int main()
{
    gibon
    cin >> N >> Q;
    for(int i=1;i<=N;i++)
    {
        int c;  cin >> c;
        E[i].resize(c);
        for(int &x : E[i])  cin >> x;
    }
    ///----make child
    dfs1(1, -1);
    chd[1]=E[1];
    for(int i=2;i<=N;i++)
    {
        int idx;
        for(int j=0;j<E[i].size();j++)  if(par[i]==E[i][j]) idx=j;
        for(int j=idx+1;j<E[i].size();j++)  chd[i].push_back(E[i][j]);
        for(int j=0;j<idx;j++)  chd[i].push_back(E[i][j]);
    }
    ///---make ETT
    ETT.push_back(-1);
    dfs2(1);
    M=ETT.size()-1;

    ///---make dir / fenwick tree
    F.siz=M;
    if(E[1].size()==1)  dir[M]=in[E[1][0]];
    else    dir[M]=in[E[1][1]];
    F.upd(M, 1);
    for(int i=2;i<=N;i++)
    {
        int nxt=(E[i].size()==1 ? E[i][0] : E[i][1]);
        if(nxt!=par[i]) dir[in[i]]=in[nxt];
        else    dir[in[i]]=out[i];
        F.upd(in[i], 1);
    }
    ///---get query
    qry.resize(Q);
    for(int i=0;i<Q;i++)
    {
        cin >> qry[i].fi;
        qry[i].se=i;
    }
    sort(all(qry));
    int qi=0;
    ll K=0;
    ll now=M;
    ///---sweeping
    while(qi!=Q)
    {
        if(F.solv(now, now)==1)
        {
            F.upd(now, -1);
            now=dir[now];
            K++;
            while(qi!=Q && qry[qi].fi==K)
            {
                ans[qry[qi].se]=ETT[now];
                qi++;
            }
            continue;
        }
        if(now==M)
        {
            now=1;
            K++;
            while(qi!=Q && qry[qi].fi==K)
            {
                ans[qry[qi].se]=ETT[now];
                qi++;
            }
            continue;
        }
        if(now==1 && F.solv(1, M)==0)
        {
            while(qi!=Q)
            {
                auto [x, id]=qry[qi];
                ans[id]=ETT[(x-K)%M+1];
                qi++;
            }
            break;
        }
        int s=now+1, e=M-1;
        if(F.solv(now, M-1)==0)   e=M;
        else
        {
            while(s!=e)
            {
                int mid=(s+e)/2;
                if(F.solv(now, mid)==0) s=mid+1;
                else    e=mid;
            }
        }
        while(qi!=Q && qry[qi].fi<=K+e-now)
        {
            auto [x, id]=qry[qi];
            ans[id]=ETT[(x-K)+now];
            qi++;
        }
        K+=e-now;
        now=e;
    }
    for(int i=0;i<Q;i++)    cout << ans[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j=0;j<E[i].size();j++)  if(par[i]==E[i][j]) idx=j;
      |                     ~^~~~~~~~~~~~
Main.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j=idx+1;j<E[i].size();j++)  chd[i].push_back(E[i][j]);
      |                         ~^~~~~~~~~~~~
Main.cpp:68:17: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |         for(int j=idx+1;j<E[i].size();j++)  chd[i].push_back(E[i][j]);
      |                 ^

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