Submission #1057870

# Submission time Handle Problem Language Result Execution time Memory
1057870 2024-08-14T06:59:01 Z 정민찬(#11077) Infiltration (CCO24_day2problem1) C++17
17 / 25
9 ms 896 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

vector<int> adj[100];
vector<int> path[100];
int dep[100];
int par[100];

void dfs(int x, int p) {
    for (auto &y : adj[x]) {
        if (y == p) continue;
        dep[y] = dep[x] + 1;
        par[y] = x;
        dfs(y, x);
    }
}

int getdep(int x, int p) {
    int ret = 1;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        ret = max(ret, getdep(y, x) + 1);
    }
    return ret;
}

vector<pair<int,int>> g[100];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    int N;
    cin >> N;
    if (N != 100) {
        //return 0;
    }
    for (int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int R = 0;
    int len = getdep(0, -1);
    for (int i=1; i<N; i++) {
        int ret = getdep(i, -1);
        if (ret < len) {
            len = ret;
            R = i;
        }
    }
    par[R] = -1;
    dfs(R, -1);
    int mxdep = 0;
    for (int i=0; i<N; i++) {
        mxdep = max(mxdep, dep[i]);
        g[dep[i]].push_back({i, i});
    }
    for (int lv=0; lv<6; lv++) {
        for (int j=0; j*(1<<lv)<=mxdep; j++) {
            if ((j & 1) || !j) {
                for (auto &[x, st] : g[j*(1<<lv)]) {
                    for (int k=0; k<(1<<lv)*2; k++)
                        path[st].push_back(x);
                }
            }
            else {
                for (auto &[x, st] : g[j*(1<<lv)]) {
                    vector<int> vec;
                    int t = x;
                    for (int k=0; k<(1<<lv); k++) {
                        vec.push_back(par[t]);
                        path[st].push_back(par[t]);
                        t = par[t];
                    }
                    for (int k=(1<<lv)-2; k>=0; k--) {
                        path[st].push_back(vec[k]);
                    }
                    path[st].push_back(x);
                }
            }
        }
        for (int j=0; j*(1<<lv)<=mxdep; j++) {
            if (j & 1) {
                for (auto &[x, st] : g[j*(1<<lv)]) {
                    int t = x;
                    for (int k=0; k<(1<<lv); k++) {
                        path[st].push_back(par[t]);
                        t = par[t];
                    }
                    g[(j-1)*(1<<lv)].push_back({t, st});
                }
            }
            else {
                for (auto &[x, st] : g[j*(1<<lv)]) {
                    for (int k=0; k<(1<<lv); k++) {
                        path[st].push_back(x);
                    }
                }
            }
        }
    }
    int T = path[0].size() * 2 + 200;
    cout << T << '\n';
    for (int i=0; i<N; i++) {
        assert(path[i].back() == R);
        for (auto &x : path[i]) {
            cout << x << ' ' << x << ' ';
        }
        for (int j=0; j<200; j++) {
            cout << R << ' ';
        }
        cout << '\n';
    }
    for (int i=0; i<N; i++) {
        assert(path[i].back() == R);
        cout << i << ' ';
        for (int j=0; j<path[i].size(); j++) {
            cout << path[i][j] << ' ';
            if (j + 1 != path[i].size())
                cout << path[i][j] << ' ';
        }
        for (int j=0; j<200; j++) {
            cout << R << ' ';
        }
        cout << '\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (int j=0; j<path[i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~
Main.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             if (j + 1 != path[i].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 708 KB Partially correct
2 Partially correct 4 ms 860 KB Partially correct
3 Partially correct 6 ms 604 KB Partially correct
4 Partially correct 8 ms 860 KB Partially correct
5 Partially correct 8 ms 788 KB Partially correct
6 Partially correct 8 ms 860 KB Partially correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 8 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 4 ms 836 KB Output is correct
12 Correct 4 ms 856 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 4 ms 856 KB Output is correct
15 Correct 4 ms 860 KB Output is correct
16 Partially correct 5 ms 860 KB Partially correct
17 Partially correct 9 ms 860 KB Partially correct
18 Partially correct 8 ms 860 KB Partially correct
19 Partially correct 4 ms 600 KB Partially correct
20 Partially correct 8 ms 604 KB Partially correct
21 Partially correct 8 ms 860 KB Partially correct
22 Partially correct 4 ms 604 KB Partially correct
23 Partially correct 5 ms 860 KB Partially correct
24 Partially correct 5 ms 860 KB Partially correct
25 Partially correct 8 ms 896 KB Partially correct