oj.uz

Submission #479877

# Submission time Handle Problem Language Result Execution time Memory
479877 2021-10-13T17:59:19 Z SamAnd Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 104212 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];
vector<int> a[N];
vector<int> b[N];

int vn;
int v[N];
void dfs(int x)
{
    while (s[x] != -1)
    {
        int h = a[x][s[x]];
        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();
        a[x].push_back(y);
        a[y].push_back(x);
        ++z;
        b[x].push_back(z);
        b[y].push_back(z);
    }
    for (int i = 1; i <= n; ++i)
        s[i] = a[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 13 ms 24172 KB Output is correct
2 Correct 14 ms 24224 KB Output is correct
3 Correct 15 ms 24268 KB Output is correct
4 Correct 14 ms 24580 KB Output is correct
5 Correct 14 ms 24304 KB Output is correct
6 Correct 15 ms 24708 KB Output is correct
7 Correct 16 ms 25932 KB Output is correct
8 Correct 18 ms 24500 KB Output is correct
9 Correct 35 ms 34752 KB Output is correct
10 Correct 15 ms 24524 KB Output is correct
11 Correct 17 ms 24476 KB Output is correct
12 Correct 45 ms 35152 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24268 KB Output is correct
2 Correct 14 ms 24240 KB Output is correct
3 Correct 14 ms 24268 KB Output is correct
4 Correct 16 ms 24652 KB Output is correct
5 Correct 14 ms 24396 KB Output is correct
6 Correct 14 ms 24780 KB Output is correct
7 Correct 17 ms 26036 KB Output is correct
8 Correct 15 ms 24524 KB Output is correct
9 Correct 36 ms 34752 KB Output is correct
10 Correct 15 ms 24524 KB Output is correct
11 Correct 14 ms 24524 KB Output is correct
12 Correct 40 ms 35196 KB Output is correct
13 Correct 91 ms 40120 KB Output is correct
14 Correct 68 ms 34432 KB Output is correct
15 Correct 67 ms 37896 KB Output is correct
16 Correct 82 ms 40128 KB Output is correct
17 Correct 70 ms 30688 KB Output is correct
18 Correct 85 ms 36292 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24200 KB Output is correct
2 Correct 13 ms 24268 KB Output is correct
3 Correct 14 ms 24268 KB Output is correct
4 Correct 14 ms 24612 KB Output is correct
5 Correct 13 ms 24396 KB Output is correct
6 Correct 15 ms 24780 KB Output is correct
7 Correct 16 ms 25912 KB Output is correct
8 Correct 13 ms 24600 KB Output is correct
9 Correct 35 ms 34756 KB Output is correct
10 Correct 18 ms 24524 KB Output is correct
11 Correct 13 ms 24568 KB Output is correct
12 Correct 41 ms 35140 KB Output is correct
13 Correct 82 ms 40232 KB Output is correct
14 Correct 79 ms 34468 KB Output is correct
15 Correct 66 ms 37836 KB Output is correct
16 Correct 86 ms 40240 KB Output is correct
17 Correct 76 ms 30788 KB Output is correct
18 Correct 85 ms 36332 KB Output is correct
19 Execution timed out 567 ms 104212 KB Time limit exceeded
20 Halted 0 ms 0 KB -