oj.uz

Submission #419629

# Submission time Handle Problem Language Result Execution time Memory
419629 2021-06-07T10:31:26 Z VladM Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 124912 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

#define DIM 500007

int u, v, n, m, par[DIM], vis[DIM];

set<int> vec[DIM];

void dfs(int v, int p)
{
    vis[v]=1;
    par[v]=p;
    for(auto to : vec[v])
    {
        if(to==p) continue;
        if(vis[to]==1)
        {
            vec[v].erase(to);
            vec[to].erase(v);
            while(v!=to)
            {
                p=par[v];
                printf("%d ", v);
                vec[v].erase(p);
                vec[p].erase(v);
                vis[v]=0;
                par[v]=0;
                v=p;
            }
            printf("%d\n", v);
            if(!vec[v].empty()) dfs(v, par[v]);
        }
        else dfs(to, v);
        break;
    }
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &u, &v);
        if(vec[v].find(u)!=vec[v].end())
        {
            printf("%d %d\n", u, v);
            vec[u].erase(v);
            vec[v].erase(u);
        }
        else
        {
            vec[u].insert(v);
            vec[v].insert(u);
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(vec[i].size()!=0)
        {
            dfs(i, -1);
        }
    }
    return 0;
}

Compilation message

postmen.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
postmen.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
postmen.cpp: In function 'int main()':
postmen.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 15 ms 24268 KB Output is correct
5 Correct 14 ms 23856 KB Output is correct
6 Correct 17 ms 24396 KB Output is correct
7 Correct 27 ms 25928 KB Output is correct
8 Correct 14 ms 24140 KB Output is correct
9 Correct 134 ms 33588 KB Output is correct
10 Correct 16 ms 24268 KB Output is correct
11 Correct 15 ms 24004 KB Output is correct
12 Correct 118 ms 33668 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23796 KB Output is correct
3 Correct 13 ms 23796 KB Output is correct
4 Correct 16 ms 24332 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 17 ms 24448 KB Output is correct
7 Correct 27 ms 25856 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 129 ms 33568 KB Output is correct
10 Correct 15 ms 24268 KB Output is correct
11 Correct 15 ms 24128 KB Output is correct
12 Correct 127 ms 33728 KB Output is correct
13 Correct 109 ms 43844 KB Output is correct
14 Correct 105 ms 43720 KB Output is correct
15 Correct 117 ms 43608 KB Output is correct
16 Correct 101 ms 43896 KB Output is correct
17 Correct 115 ms 43588 KB Output is correct
18 Correct 102 ms 36604 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct
3 Correct 13 ms 23796 KB Output is correct
4 Correct 15 ms 24272 KB Output is correct
5 Correct 15 ms 23884 KB Output is correct
6 Correct 17 ms 24396 KB Output is correct
7 Correct 27 ms 25932 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 150 ms 33668 KB Output is correct
10 Correct 16 ms 24268 KB Output is correct
11 Correct 16 ms 24012 KB Output is correct
12 Correct 119 ms 33744 KB Output is correct
13 Correct 105 ms 43844 KB Output is correct
14 Correct 116 ms 43744 KB Output is correct
15 Correct 116 ms 43492 KB Output is correct
16 Correct 135 ms 43852 KB Output is correct
17 Correct 114 ms 43552 KB Output is correct
18 Correct 105 ms 36632 KB Output is correct
19 Execution timed out 554 ms 124912 KB Time limit exceeded
20 Halted 0 ms 0 KB -