oj.uz

Submission #419636

# Submission time Handle Problem Language Result Execution time Memory
419636 2021-06-07T10:40:07 Z VladM Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 125016 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)
{
    vis[v]=1;
    for(auto to : vec[v])
    {
        if(to==par[v]) continue;
        if(vis[to]==1)
        {
            vec[v].erase(to);
            vec[to].erase(v);
            while(v!=to)
            {
                int 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);
        }
        else
        {
            par[to]=v;
            dfs(to);
        }
        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);
        }
    }
    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:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         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 14 ms 23756 KB Output is correct
3 Correct 14 ms 23704 KB Output is correct
4 Correct 16 ms 24272 KB Output is correct
5 Correct 15 ms 23852 KB Output is correct
6 Correct 74 ms 24308 KB Output is correct
7 Correct 33 ms 25924 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 137 ms 33544 KB Output is correct
10 Correct 16 ms 24268 KB Output is correct
11 Correct 17 ms 24012 KB Output is correct
12 Correct 123 ms 33672 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 23680 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 15 ms 24328 KB Output is correct
5 Correct 17 ms 23844 KB Output is correct
6 Correct 18 ms 24332 KB Output is correct
7 Correct 28 ms 25868 KB Output is correct
8 Correct 19 ms 24140 KB Output is correct
9 Correct 126 ms 33588 KB Output is correct
10 Correct 15 ms 24268 KB Output is correct
11 Correct 14 ms 24124 KB Output is correct
12 Correct 143 ms 33728 KB Output is correct
13 Correct 122 ms 43820 KB Output is correct
14 Correct 137 ms 43652 KB Output is correct
15 Correct 121 ms 43460 KB Output is correct
16 Correct 102 ms 43868 KB Output is correct
17 Correct 113 ms 43716 KB Output is correct
18 Correct 110 ms 36664 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 12 ms 23756 KB Output is correct
3 Correct 14 ms 23736 KB Output is correct
4 Correct 16 ms 24380 KB Output is correct
5 Correct 14 ms 23876 KB Output is correct
6 Correct 17 ms 24448 KB Output is correct
7 Correct 26 ms 25804 KB Output is correct
8 Correct 15 ms 24140 KB Output is correct
9 Correct 144 ms 33476 KB Output is correct
10 Correct 16 ms 24356 KB Output is correct
11 Correct 69 ms 24132 KB Output is correct
12 Correct 146 ms 33756 KB Output is correct
13 Correct 116 ms 43904 KB Output is correct
14 Correct 116 ms 43624 KB Output is correct
15 Correct 131 ms 43480 KB Output is correct
16 Correct 113 ms 43812 KB Output is correct
17 Correct 119 ms 43616 KB Output is correct
18 Correct 105 ms 36676 KB Output is correct
19 Execution timed out 579 ms 125016 KB Time limit exceeded
20 Halted 0 ms 0 KB -