oj.uz

Submission #419648

# Submission time Handle Problem Language Result Execution time Memory
419648 2021-06-07T10:52:10 Z VladM Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 125056 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

int u, v, n, m;

vector<int> par, vis;

vector<set<int> > vec;

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);
    vec.resize(n+1);
    par.resize(n+1);
    vis.resize(n+1);
    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: 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:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 14 ms 2420 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 116 ms 10052 KB Output is correct
10 Correct 3 ms 972 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 117 ms 10304 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 17 ms 2428 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 120 ms 10056 KB Output is correct
10 Correct 3 ms 972 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 128 ms 10256 KB Output is correct
13 Correct 101 ms 25132 KB Output is correct
14 Correct 91 ms 23748 KB Output is correct
15 Correct 107 ms 23088 KB Output is correct
16 Correct 93 ms 25028 KB Output is correct
17 Correct 101 ms 23272 KB Output is correct
18 Correct 101 ms 16668 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 15 ms 2380 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 121 ms 10060 KB Output is correct
10 Correct 4 ms 972 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 116 ms 10292 KB Output is correct
13 Correct 96 ms 25028 KB Output is correct
14 Correct 93 ms 23640 KB Output is correct
15 Correct 99 ms 23104 KB Output is correct
16 Correct 100 ms 25204 KB Output is correct
17 Correct 99 ms 23360 KB Output is correct
18 Correct 92 ms 16716 KB Output is correct
19 Execution timed out 548 ms 125056 KB Time limit exceeded
20 Halted 0 ms 0 KB -