oj.uz

Submission #697652

# Submission time Handle Problem Language Result Execution time Memory
697652 2023-02-10T15:50:57 Z tamthegod Senior Postmen (BOI14_postmen) C++17
100 / 100
 397 ms 51496 KB 
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 5e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, m;
int id = 0;
vector<int> path;
vector<int> adj[maxN];
struct TEdge
{
    int u, v;
    bool del;
} e[maxN];
void ReadInput()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v, 0};
        adj[u].pb(i);
        adj[v].pb(i);
    }
}

void FindEulerTour()
{
    vector<int> vc;
    vc.pb(1);
    while(!vc.empty())
    {
        int u = vc.back();
        while(!adj[u].empty() && e[adj[u].back()].del) adj[u].pop_back();
        if(!adj[u].empty())
        {
            int id = adj[u].back();
            adj[u].pop_back();
            e[id].del = 1;
            vc.pb(e[id].u ^ e[id].v ^ u);
        }
        else
        {
            path.pb(u);
            vc.pop_back();
        }
    }
}
int vis[maxN];
void Solve()
{
    FindEulerTour();
    int tmp = 0;
    vector<int> bin;
    for(int u : path)
    {
        if(vis[u])
        {
            while(true)
            {
                int v = bin.back();
                bin.pop_back();
                cout << v << " ";
                vis[v] = 0;
                if(v == u) break;
            }
            cout << '\n';
        }
        vis[u] = 1;
        bin.pb(u);
    }
}
int32_t main()
{
    //  freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message

postmen.cpp: In function 'void Solve()':
postmen.cpp:64:9: warning: unused variable 'tmp' [-Wunused-variable]
   64 |     int tmp = 0;
      |         ^~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12072 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 9 ms 12216 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12244 KB Output is correct
7 Correct 11 ms 12756 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 33 ms 16104 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 37 ms 16332 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 8 ms 12164 KB Output is correct
5 Correct 7 ms 12148 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 10 ms 12756 KB Output is correct
8 Correct 8 ms 12120 KB Output is correct
9 Correct 31 ms 16044 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12180 KB Output is correct
12 Correct 35 ms 16336 KB Output is correct
13 Correct 51 ms 19784 KB Output is correct
14 Correct 52 ms 18396 KB Output is correct
15 Correct 44 ms 17692 KB Output is correct
16 Correct 58 ms 19716 KB Output is correct
17 Correct 54 ms 18068 KB Output is correct
18 Correct 47 ms 18152 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 12076 KB Output is correct
3 Correct 6 ms 12072 KB Output is correct
4 Correct 7 ms 12244 KB Output is correct
5 Correct 6 ms 12152 KB Output is correct
6 Correct 8 ms 12244 KB Output is correct
7 Correct 12 ms 12856 KB Output is correct
8 Correct 8 ms 12212 KB Output is correct
9 Correct 33 ms 16068 KB Output is correct
10 Correct 7 ms 12160 KB Output is correct
11 Correct 7 ms 12216 KB Output is correct
12 Correct 38 ms 16392 KB Output is correct
13 Correct 58 ms 19804 KB Output is correct
14 Correct 49 ms 18508 KB Output is correct
15 Correct 50 ms 17768 KB Output is correct
16 Correct 49 ms 19784 KB Output is correct
17 Correct 49 ms 18044 KB Output is correct
18 Correct 54 ms 18228 KB Output is correct
19 Correct 390 ms 51496 KB Output is correct
20 Correct 351 ms 45148 KB Output is correct
21 Correct 319 ms 40760 KB Output is correct
22 Correct 379 ms 51452 KB Output is correct
23 Correct 129 ms 31188 KB Output is correct
24 Correct 397 ms 42376 KB Output is correct
25 Correct 378 ms 44004 KB Output is correct