oj.uz

Submission #479878

# Submission time Handle Problem Language Result Execution time Memory
479878 2021-10-13T18:01:22 Z SamAnd Senior Postmen (BOI14_postmen) C++17
100 / 100
 387 ms 79492 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 500005;

int n, m;
int z;
bool c[N];
int s[N];
pair<int, int> a[N];
vector<int> b[N];

int vn;
int v[N];
void dfs(int x)
{
    while (s[x] != -1)
    {
        int h = a[b[x][s[x]]].first;
        if (h == x)
            h = a[b[x][s[x]]].second;
        if (c[b[x][s[x]]])
        {
            --s[x];
            continue;
        }
        c[b[x][s[x]]] = true;
        --s[x];
        dfs(h);
    }
    v[vn++] = x;
}

int ka()
{
    int x = 0;
    while (1)
    {
        char t = getchar();
        if (t == ' ' || t == '\n')
            return x;
        x *= 10;
        x += (t - '0');
    }
}

char t[10];
void tp(int x)
{
    int tn = 0;
    while (x)
    {
        t[tn++] = (x % 10) + '0';
        x /= 10;
    }
    for (int i = tn - 1; i >= 0; --i)
        putchar(t[i]);
    putchar(' ');
}

int main()
{
    n = ka();
    m = ka();
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        x = ka();
        y = ka();
        ++z;
        a[z] = m_p(x, y);
        b[x].push_back(z);
        b[y].push_back(z);
    }
    for (int i = 1; i <= n; ++i)
        s[i] = b[i].size() - 1;
    dfs(1);
    memset(c, false, sizeof c);
    vector<int> s;
    for (int i = 0; i < vn; ++i)
    {
        if (c[v[i]])
        {
            tp(v[i]);
            while (s.back() != v[i])
            {
                tp(s.back());
                c[s.back()] = false;
                s.pop_back();
            }
            putchar('\n');
        }
        else
        {
            s.push_back(v[i]);
            c[v[i]] = true;
        }
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12492 KB Output is correct
2 Correct 6 ms 12492 KB Output is correct
3 Correct 6 ms 12492 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12620 KB Output is correct
6 Correct 8 ms 12960 KB Output is correct
7 Correct 10 ms 13900 KB Output is correct
8 Correct 7 ms 12748 KB Output is correct
9 Correct 23 ms 21340 KB Output is correct
10 Correct 7 ms 12748 KB Output is correct
11 Correct 8 ms 12748 KB Output is correct
12 Correct 27 ms 21508 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Output is correct
2 Correct 8 ms 12492 KB Output is correct
3 Correct 8 ms 12460 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12620 KB Output is correct
6 Correct 8 ms 12876 KB Output is correct
7 Correct 10 ms 13900 KB Output is correct
8 Correct 7 ms 12748 KB Output is correct
9 Correct 24 ms 21324 KB Output is correct
10 Correct 8 ms 12748 KB Output is correct
11 Correct 7 ms 12748 KB Output is correct
12 Correct 29 ms 21452 KB Output is correct
13 Correct 47 ms 24520 KB Output is correct
14 Correct 38 ms 20292 KB Output is correct
15 Correct 39 ms 22968 KB Output is correct
16 Correct 45 ms 24484 KB Output is correct
17 Correct 39 ms 17352 KB Output is correct
18 Correct 44 ms 21828 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12492 KB Output is correct
2 Correct 6 ms 12492 KB Output is correct
3 Correct 7 ms 12552 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12620 KB Output is correct
6 Correct 7 ms 12896 KB Output is correct
7 Correct 9 ms 13912 KB Output is correct
8 Correct 8 ms 12668 KB Output is correct
9 Correct 24 ms 21300 KB Output is correct
10 Correct 7 ms 12748 KB Output is correct
11 Correct 7 ms 12728 KB Output is correct
12 Correct 30 ms 21528 KB Output is correct
13 Correct 50 ms 24544 KB Output is correct
14 Correct 36 ms 20372 KB Output is correct
15 Correct 36 ms 23072 KB Output is correct
16 Correct 45 ms 24516 KB Output is correct
17 Correct 47 ms 17348 KB Output is correct
18 Correct 42 ms 21828 KB Output is correct
19 Correct 377 ms 72856 KB Output is correct
20 Correct 332 ms 58488 KB Output is correct
21 Correct 297 ms 70400 KB Output is correct
22 Correct 387 ms 79492 KB Output is correct
23 Correct 102 ms 59780 KB Output is correct
24 Correct 361 ms 43516 KB Output is correct
25 Correct 373 ms 65556 KB Output is correct