oj.uz

Submission #1058061

# Submission time Handle Problem Language Result Execution time Memory
1058061 2024-08-14T08:11:20 Z 변재우(#11079) Infiltration (CCO24_day2problem1) C++17
8 / 25
 1 ms 348 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=110;
int N, mn=Nmax, R, D[Nmax], P[Nmax];
vector<int> adj[Nmax];

int DFS(int curr, int prev) {
    int ret=D[curr];
    for(int next:adj[curr]) if(next!=prev) P[next]=curr, D[next]=D[curr]+1, ret=max(ret, DFS(next, curr));
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    // assert(N==100);
    for(int i=1; i<N; i++) {
        int u, v; cin>>u>>v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    for(int i=0; i<N; i++) {
        D[i]=0;
        int tmp=DFS(i, -1);
        if(tmp<mn) mn=tmp, R=i;
    }
    D[R]=0, DFS(R, -1);
    cout<<2*mn+1<<"\n";
    for(int i=0; i<N; i++) {
        int x=i;
        for(int j=mn; j>=1; j--) {
            if(D[x]==j) x=P[x];
            cout<<x<<" "<<x<<" ";
        }
        cout<<R<<"\n";
    }
    for(int i=0; i<N; i++) {
        int x=i;
        cout<<i<<" ";
        for(int j=mn; j>=1; j--) {
            if(D[x]==j) x=P[x];
            cout<<x<<" "<<x<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

Subtask #1
8.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Partially correct 0 ms 348 KB Partially correct
17 Partially correct 1 ms 348 KB Partially correct
18 Partially correct 0 ms 348 KB Partially correct
19 Partially correct 0 ms 348 KB Partially correct
20 Partially correct 0 ms 348 KB Partially correct
21 Partially correct 1 ms 348 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 0 ms 348 KB Partially correct
24 Partially correct 1 ms 348 KB Partially correct
25 Partially correct 1 ms 348 KB Partially correct