oj.uz

Submission #534813

# Submission time Handle Problem Language Result Execution time Memory
534813 2022-03-09T02:53:48 Z Bill_00 Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 76876 KB 
#include <bits/stdc++.h>
#define N 500005
using namespace std;

int vis[N], p[N];
int n, m, pre; 
set<int> adj[N];
 

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        adj[a].insert(b);
        adj[b].insert(a);
    }

    for(int i = 1; i <= n; i++){
        while(adj[i].size()){
            stack<int> s;
            s.push(i);
            while(s.size()){
                int now = s.top();
                // cout << now << ' ';
                
                if(vis[now] == 1){
                    // cout << 1 << '\n';
                    cout << now << ' ';
                    s.pop();
                    while(s.top() != now){
                        vis[s.top()] = 0;
                        cout << s.top() << ' ';
                        s.pop();
                    }
                    vis[now] = 0;
                    cout << '\n';
                }
                else{
                    if(adj[now].size() == 0){
                        vis[now] = 2;
                        s.pop();
                        // cout << 2 << '\n';
                    }
                    else{
                        // cout << 3 << '\n';
                        vis[now] = 1;
                        int k = *adj[now].begin();
                        adj[now].erase(k);
                        adj[k].erase(now);
                        s.push(k);
                    }
                }
            }

        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23744 KB Output is correct
3 Correct 12 ms 23692 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 12 ms 23916 KB Output is correct
6 Correct 14 ms 24248 KB Output is correct
7 Correct 28 ms 25164 KB Output is correct
8 Correct 17 ms 24012 KB Output is correct
9 Correct 114 ms 33552 KB Output is correct
10 Correct 14 ms 24012 KB Output is correct
11 Correct 13 ms 24012 KB Output is correct
12 Correct 158 ms 33648 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 11 ms 23768 KB Output is correct
3 Correct 12 ms 23732 KB Output is correct
4 Correct 13 ms 24116 KB Output is correct
5 Correct 14 ms 23916 KB Output is correct
6 Correct 15 ms 24140 KB Output is correct
7 Correct 28 ms 25164 KB Output is correct
8 Correct 12 ms 24012 KB Output is correct
9 Correct 99 ms 33548 KB Output is correct
10 Correct 14 ms 24012 KB Output is correct
11 Correct 16 ms 24012 KB Output is correct
12 Correct 104 ms 33632 KB Output is correct
13 Correct 81 ms 34372 KB Output is correct
14 Correct 90 ms 34172 KB Output is correct
15 Correct 83 ms 33876 KB Output is correct
16 Correct 76 ms 34344 KB Output is correct
17 Correct 98 ms 34080 KB Output is correct
18 Correct 86 ms 34084 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23736 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 17 ms 24020 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 20 ms 25216 KB Output is correct
8 Correct 14 ms 24000 KB Output is correct
9 Correct 130 ms 33456 KB Output is correct
10 Correct 14 ms 24012 KB Output is correct
11 Correct 13 ms 24072 KB Output is correct
12 Correct 96 ms 33580 KB Output is correct
13 Correct 87 ms 34372 KB Output is correct
14 Correct 90 ms 34220 KB Output is correct
15 Correct 85 ms 33904 KB Output is correct
16 Correct 87 ms 34284 KB Output is correct
17 Correct 90 ms 33992 KB Output is correct
18 Correct 93 ms 34116 KB Output is correct
19 Correct 448 ms 76876 KB Output is correct
20 Execution timed out 583 ms 76296 KB Time limit exceeded
21 Halted 0 ms 0 KB -