Submission #1058026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058026	2024-08-14T08:02:27 Z	mickey080929	Infiltration (CCO24_day2problem1)	C++17	25 / 25	10 ms	876 KB

Main

#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) {
                for (auto &[x, st] : g[j*(1<<lv)]) {
                    for (int k=0; k<2*(1<<lv); k++)
                        path[st].push_back(x);
                }
            }
            else if (j & 1) {
                for (auto &[x, st] : g[j*(1<<lv)]) {
                    for (int k=0; k<(1<<lv); 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});
                }
            }
        }
    }
    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:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int j=0; j<path[i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~
Main.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             if (j + 1 != path[i].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	604 KB	Output is correct
2	Correct	5 ms	600 KB	Output is correct
3	Correct	7 ms	604 KB	Output is correct
4	Correct	4 ms	856 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	10 ms	800 KB	Output is correct
7	Correct	4 ms	600 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Correct	4 ms	604 KB	Output is correct
10	Correct	4 ms	604 KB	Output is correct
11	Correct	7 ms	736 KB	Output is correct
12	Correct	4 ms	604 KB	Output is correct
13	Correct	6 ms	720 KB	Output is correct
14	Correct	3 ms	604 KB	Output is correct
15	Correct	3 ms	604 KB	Output is correct
16	Correct	3 ms	600 KB	Output is correct
17	Correct	4 ms	692 KB	Output is correct
18	Correct	7 ms	604 KB	Output is correct
19	Correct	3 ms	604 KB	Output is correct
20	Correct	3 ms	604 KB	Output is correct
21	Correct	3 ms	604 KB	Output is correct
22	Correct	7 ms	604 KB	Output is correct
23	Correct	4 ms	876 KB	Output is correct
24	Correct	5 ms	604 KB	Output is correct
25	Correct	5 ms	604 KB	Output is correct