답안 #492645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492645	2021-12-08T09:51:00 Z	Rainbowbunny	어르신 집배원 (BOI14_postmen)	C++17	100 / 100	447 ms	109104 KB

postmen

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;

int n, m;
int ii[MAXN];
vector <pair <int, int> > Adj[MAXN];
vector <int> Ans[MAXN];
bool In[MAXN], Used[MAXN];

void Find(int node, int id)
{
    while(ii[node] < (int)Adj[node].size() and Used[Adj[node][ii[node]].second])
    {
        ii[node]++;
    }
    if(ii[node] < (int)Adj[node].size())
    {
        Used[Adj[node][ii[node]].second] = true;
        Find(Adj[node][ii[node]].first, id);
    }
    if(In[node])
    {
        cout << node << ' ';
        while(Ans[id].back() != node)
        {
            cout << Ans[id].back() << ' ';
            In[Ans[id].back()] = false;
            Ans[id].pop_back();
        }
        cout << '\n';
    }
    else
    {
        In[node] = true;
        Ans[id].push_back(node);
    }
}

int main()
{
    // freopen("test_input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].emplace_back(v, i);
        Adj[v].emplace_back(u, i);
    }
    for(int i = 1; i <= n; i++)
    {
        if((int)Adj[i].size())
        {
            Find(i, i);
        }
    }
}

Subtask #1

38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	23720 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	14 ms	23756 KB	Output is correct
4	Correct	13 ms	24204 KB	Output is correct
5	Correct	11 ms	23884 KB	Output is correct
6	Correct	13 ms	24332 KB	Output is correct
7	Correct	17 ms	25612 KB	Output is correct
8	Correct	13 ms	24140 KB	Output is correct
9	Correct	41 ms	34792 KB	Output is correct
10	Correct	14 ms	24012 KB	Output is correct
11	Correct	14 ms	24044 KB	Output is correct
12	Correct	45 ms	35012 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23756 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	12 ms	23756 KB	Output is correct
4	Correct	14 ms	24140 KB	Output is correct
5	Correct	12 ms	23864 KB	Output is correct
6	Correct	14 ms	24272 KB	Output is correct
7	Correct	17 ms	25560 KB	Output is correct
8	Correct	14 ms	24080 KB	Output is correct
9	Correct	41 ms	34756 KB	Output is correct
10	Correct	13 ms	24020 KB	Output is correct
11	Correct	15 ms	24076 KB	Output is correct
12	Correct	43 ms	35016 KB	Output is correct
13	Correct	74 ms	40188 KB	Output is correct
14	Correct	60 ms	30788 KB	Output is correct
15	Correct	59 ms	37880 KB	Output is correct
16	Correct	71 ms	40096 KB	Output is correct
17	Correct	63 ms	31048 KB	Output is correct
18	Correct	66 ms	36552 KB	Output is correct

Subtask #3

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23756 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	12 ms	23804 KB	Output is correct
4	Correct	14 ms	24260 KB	Output is correct
5	Correct	14 ms	23884 KB	Output is correct
6	Correct	14 ms	24312 KB	Output is correct
7	Correct	17 ms	25608 KB	Output is correct
8	Correct	14 ms	24012 KB	Output is correct
9	Correct	40 ms	34708 KB	Output is correct
10	Correct	14 ms	24012 KB	Output is correct
11	Correct	13 ms	24124 KB	Output is correct
12	Correct	46 ms	35140 KB	Output is correct
13	Correct	72 ms	40144 KB	Output is correct
14	Correct	60 ms	30936 KB	Output is correct
15	Correct	60 ms	37948 KB	Output is correct
16	Correct	70 ms	40164 KB	Output is correct
17	Correct	64 ms	31100 KB	Output is correct
18	Correct	67 ms	36544 KB	Output is correct
19	Correct	447 ms	103488 KB	Output is correct
20	Correct	366 ms	56892 KB	Output is correct
21	Correct	375 ms	96168 KB	Output is correct
22	Correct	444 ms	109104 KB	Output is correct
23	Correct	157 ms	77828 KB	Output is correct
24	Correct	423 ms	63172 KB	Output is correct
25	Correct	426 ms	91280 KB	Output is correct