提出 #34578554

---

ソースコード 拡げる

#include"bits/stdc++.h"

using namespace std;

const int N = 201000;

vector<int> g[N];
int d[N];
int n, st, ed, c, flag;
int inz[N];
vector<int> zz;
int ff[N], f[N][20];
int dis[N], dt[N];


void dfs(int x, int fa) {
    for (int y: g[x]) {
        if (y == fa) continue;
        d[y] = d[x] + 1;
        if (d[y] > d[c]) c = y;
        dfs(y, x);
    }
}

void dfs2(int x, int fa) {
    // cout << "!" << x << " " << fa << " " << ed << endl;
    if (x == ed) {
        inz[x] = zz.size();
        zz.push_back(x);
        flag = 1;
        return;
    }
    for (int y: g[x]) {
        if (y == fa) continue;
        dfs2(y, x);
        if (flag) {
            inz[x] = zz.size();
            zz.push_back(x);
            return;
        }
    }
}

void dfs3(int x, int fa, int ss, int dep=0) {
    dt[x] = ss;
    dis[x] = dep;
    f[x][0] = fa;
    for (int y: g[x]) {
        if (y == fa || inz[y] != -1) continue;
        dfs3(y, x, ss, dep+1);
    }
}

int main() {
    // freopen("F.in" , "r" , stdin);
    // freopen("F.out" , "w" , stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i) inz[i] = -1;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    // for (int i = 1; i <= n; ++i) cout << d[i] << " ";cout << endl;
    d[c] = 0;
    st = c;
    dfs(c, 0);
    // for (int i = 1; i <= n; ++i) cout << d[i] << " ";cout << endl;
    ed = c;
    flag = 0;
    // cout << st << " " << ed << endl;
    dfs2(st, 0);
    for (int i = 0; i < zz.size(); ++i) {
        dfs3(zz[i], zz[i], zz[i]);
    }
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
    // for (int i = 0; i < zz.size(); ++i) cout << zz[i] << " ";cout << endl;
    // for (int i = 1; i <= n; ++i) cout << inz[i] << " ";cout << endl;
    int Q;
    cin >> Q;
    for (; Q; --Q) {
        int x, k;
        cin >> x >> k;
        if (k <= dis[x]) {
            int ans = x;
            for (int i = 19; i >= 0; --i) {
                if (k >= (1<<i)) {
                    ans = f[ans][i];
                    k -= (1<<i);
                }
            }
            cout << ans << endl;
        } else {
            k -= dis[x];
            int ans = dt[x];
            int idx = inz[ans];
            // cout << idx << " " << k << endl;
            if (idx >= k) {
                cout << zz[idx - k] << endl;
            } else if (zz.size()-idx-1 >= k) {
                cout << zz[idx + k] << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:75:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   75 |     for (int i = 0; i < zz.size(); ++i) {
      |                     ~~^~~~~~~~~~~
./Main.cpp:106:40: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  106 |             } else if (zz.size()-idx-1 >= k) {
      |                        ~~~~~~~~~~~~~~~~^~~~

ジャッジ結果