Submission #1057767

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1057767	2024-08-14T05:45:52 Z	정희우(#11078)	Infiltration (CCO24_day2problem1)	C++17	25 / 25	4 ms	856 KB

Main

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=105;

int n;
vint edge[MAX_N];
int pa[MAX_N];

vector<pii> moves[2]={
{{3,1},{13,0},{57,1},{100,1}},
{{3,0},{13,1},{20,0},{37,1},{100,1}}};

int dep(int v,int p,int d)
{
    int mxd=d;
    pa[v]=p;
    for(auto v0 : edge[v])
        if(v0!=p)
            mxd=max(mxd,dep(v0,v,d+1));
    return mxd;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    if(n!=100)return 1;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    /*dep(0,0,0);
    cout << 200 << '\n';
    for(int k=0;k<2;k++)
    {
        for(int i=0;i<n;i++)
        {
            int v=i;
            for(int j=0;j<100;j++)
            {
                if(k)cout << v << ' ';
                v=pa[v];
                cout << v << ' ';
                if(!k)cout << v << ' ';
            }
            cout << '\n';
        }
    }*/
    int root=0,d=dep(0,0,0);
    for(int i=0;i<n;i++)
    {
        int cd=dep(i,i,0);
        if(cd>=d)continue;
        root=i;d=cd;
    }
    dep(root,root,0);
    cout << 346 << '\n';
    for(int k=0;k<2;k++)
    {
        for(int i=0;i<n;i++)
        {
            int v=i;
            for(auto p : moves[k])
                for(int j=0;j<p.first;j++)
                {
                    if(k)cout << v << ' ';
                    if(p.second)v=pa[v];
                    cout << v << ' ';
                    if(!k)cout << v << ' ';
                }
            if(v!=root)return 1;
            cout << '\n';
        }
    }
    return 0;
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	600 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	3 ms	604 KB	Output is correct
6	Correct	3 ms	604 KB	Output is correct
7	Correct	3 ms	604 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	3 ms	604 KB	Output is correct
11	Correct	3 ms	856 KB	Output is correct
12	Correct	3 ms	600 KB	Output is correct
13	Correct	3 ms	348 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	604 KB	Output is correct
17	Correct	4 ms	604 KB	Output is correct
18	Correct	3 ms	604 KB	Output is correct
19	Correct	3 ms	604 KB	Output is correct
20	Correct	4 ms	604 KB	Output is correct
21	Correct	3 ms	600 KB	Output is correct
22	Correct	3 ms	600 KB	Output is correct
23	Correct	3 ms	600 KB	Output is correct
24	Correct	3 ms	604 KB	Output is correct
25	Correct	3 ms	604 KB	Output is correct