oj.uz

Submission #697890

# Submission time Handle Problem Language Result Execution time Memory
697890 2023-02-11T09:44:48 Z mousebeaver Senior Postmen (BOI14_postmen) C++14
38 / 100
 500 ms 22504 KB 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pdi pair<double, int>
#define pcc pair<char, char>
#define tiii tuple<int, int, int>
#define tlii tuple<int, int, int>
#define tl tuple<ll, ll, ll, ll>
#define tls tuple<ll, ll, ll>
#define INF numeric_limits<ll>::max()/2
#define MOD 1000000007
#define MIO 1000000
#define mp make_pair
#include <bits/stdc++.h>
using namespace std;

void hierholzer(int i, vector<vector<pii>>& adjlist, vector<vector<bool>>& active, vector<int>& output)
{
    for(int k = 0; k < (int) adjlist[i].size(); k++)
    {
        if(active[i][k])
        {
            int j = adjlist[i][k].first;
            int ind = adjlist[i][k].second;
            active[i][k] = false;
            active[j][ind] = false;
            hierholzer(j, adjlist, active, output);
            output.push_back(j);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin>>n>>m;
    vector<vector<pii>> adjlist(n, vector<pii> (0));
    vector<vector<bool>> active(n, vector<bool> (0));
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin>>a>>b;
        a--; b--;
        adjlist[a].push_back({b, adjlist[b].size()});
        adjlist[b].push_back({a, adjlist[a].size()-1});
    }
    for(int i = 0; i < n; i++)
    {
        active[i].assign(adjlist[i].size(), true);
    }

    vector<int> output(0);
    hierholzer(0, adjlist, active, output);
    output.push_back(0);
    reverse(output.begin(), output.end());

    /*for(int i : output)
    {
        cout<<i+1<<" ";
    }
    cout<<"\n";*/

    stack<int> tour;
    vector<bool> instack(n, false);
    for(int i : output)
    {
        if(instack[i])
        {
            vector<int> senior(0);
            int v = -1;
            while(v != i)
            {
                v = tour.top();
                tour.pop();
                instack[v] = false;
                senior.push_back(v);
            }
            tour.push(i);
            instack[i] = true;
            for(int j : senior)
            {
                cout<<j+1<<" ";
            }
            cout<<"\n";
        }
        else
        {
            tour.push(i);
            instack[i] = true;
        }
    }

    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 8 ms 2132 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 87 ms 11068 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 52 ms 11428 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 864 KB Output is correct
7 Correct 9 ms 2132 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 83 ms 11156 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 49 ms 11384 KB Output is correct
13 Correct 65 ms 22484 KB Output is correct
14 Correct 52 ms 15224 KB Output is correct
15 Execution timed out 1088 ms 17212 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 792 KB Output is correct
7 Correct 8 ms 2132 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 87 ms 11048 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 50 ms 11572 KB Output is correct
13 Correct 58 ms 22504 KB Output is correct
14 Correct 59 ms 15172 KB Output is correct
15 Execution timed out 1086 ms 17332 KB Time limit exceeded
16 Halted 0 ms 0 KB -