oj.uz

Submission #733351

# Submission time Handle Problem Language Result Execution time Memory
733351 2023-04-30T14:13:55 Z n0sk1ll Senior Postmen (BOI14_postmen) C++17
100 / 100
 470 ms 61608 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

vector<vector<int>> ans;

vector<vector<int>> g(500005); //za svaki cvor pamtimo vector indeksa edge-ova
pii ed[500005];
bool potrosen[500005]; //da li je edge vec iskoriscen?

vector<int> put;
bool tvis[500005]; //trenutno posecen?
void dfs(int p)
{
    if (tvis[p])
    {
        while (true)
        {
            cout<<put.back()<<" ";
            bool is_break=(put.back()==p);
            tvis[put.back()]=false,put.popb();
            if (is_break) break;
        }
        cout<<"\n";
    }

    put.pb(p),tvis[p]=true;
    while (!g[p].empty())
    {
        int ind=g[p].back();
        g[p].popb();
        if (potrosen[ind]) continue;
        potrosen[ind]=true;

        auto [u,v]=ed[ind];
        if (p==u) dfs(v);
        else dfs(u);
        goto uso;
    }

    put.popb(),tvis[p]=false;

    uso:;
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    ff(i,0,m)
    {
        int u,v; cin>>u>>v;
        g[u].pb(i),g[v].pb(i);
        ed[i]={u,v};
    }

    fff(i,1,n) dfs(i);
}

//Note to self: Check for overflow

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12372 KB Output is correct
7 Correct 11 ms 13104 KB Output is correct
8 Correct 7 ms 12280 KB Output is correct
9 Correct 34 ms 18920 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 7 ms 12224 KB Output is correct
12 Correct 38 ms 19216 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 7 ms 12072 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12372 KB Output is correct
7 Correct 11 ms 13140 KB Output is correct
8 Correct 8 ms 12288 KB Output is correct
9 Correct 37 ms 18924 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 8 ms 12244 KB Output is correct
12 Correct 39 ms 19148 KB Output is correct
13 Correct 63 ms 21956 KB Output is correct
14 Correct 50 ms 15980 KB Output is correct
15 Correct 52 ms 20544 KB Output is correct
16 Correct 55 ms 21988 KB Output is correct
17 Correct 54 ms 16204 KB Output is correct
18 Correct 58 ms 19728 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 9 ms 11988 KB Output is correct
4 Correct 7 ms 12244 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 11 ms 12304 KB Output is correct
7 Correct 10 ms 13140 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 36 ms 18892 KB Output is correct
10 Correct 10 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 37 ms 19184 KB Output is correct
13 Correct 54 ms 21956 KB Output is correct
14 Correct 51 ms 15972 KB Output is correct
15 Correct 52 ms 20456 KB Output is correct
16 Correct 60 ms 21936 KB Output is correct
17 Correct 60 ms 16156 KB Output is correct
18 Correct 54 ms 19600 KB Output is correct
19 Correct 435 ms 61608 KB Output is correct
20 Correct 408 ms 31968 KB Output is correct
21 Correct 363 ms 54716 KB Output is correct
22 Correct 433 ms 61496 KB Output is correct
23 Correct 159 ms 46196 KB Output is correct
24 Correct 462 ms 33740 KB Output is correct
25 Correct 470 ms 50100 KB Output is correct