oj.uz

Submission #462611

# Submission time Handle Problem Language Result Execution time Memory
462611 2021-08-11T00:09:50 Z JovanB Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 44728 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
vector <pair <int, int>> graf[500005];
 
bool visited[500005];
bool used[500005];
vector <vector <int>> cycles;
 
bool novi;
 
void ocisti(vector <pair <int, int>> &vec){
    while(!vec.empty() && used[vec.back().second]){
        vec.pop_back();
    }
}
 
void dfs(int tr){
    stack <int> stek;
    stek.push(tr);
    visited[tr] = 1;
    while(!stek.empty()){
        int v = stek.top();
        ocisti(graf[v]);
        if(novi){
            cycles.back().push_back(v);
            if(cycles.back()[0] == cycles.back()[cycles.back().size()-1]){
                novi = 0;
                continue;
            }
            stek.pop();
            visited[v] = 0;
            continue;
        }
        if(graf[v].empty()){
            visited[v] = 0;
            stek.pop();
            continue;
        }
        int c = graf[v].back().first;
        int g = graf[v].back().second;
        graf[v].pop_back();
        used[g] = 1;
        if(visited[c]){
            cycles.push_back({});
            cycles.back().push_back(c);
            novi = 1;
            continue;
        }
        else{
            stek.push(c);
            visited[c] = 1;
            continue;
        }
        stek.pop();
        visited[v] = 0;
    }
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
	int n, m;
	cin >> n >> m;
	int cnt = 0;
	for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back({b, ++cnt});
        graf[b].push_back({a, cnt});
	}
	int tr = 1;
	dfs(tr);
	while(tr <= n){
        dfs(tr);
        if(!graf[tr].size()) tr++;
	}
	for(auto cycle : cycles){
        cycle.pop_back();
        for(auto c : cycle) cout << c << " ";
        cout << "\n";
	}
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 9 ms 12180 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 11 ms 12204 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 9 ms 12236 KB Output is correct
7 Correct 14 ms 12764 KB Output is correct
8 Correct 10 ms 12108 KB Output is correct
9 Correct 44 ms 15756 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 9 ms 12236 KB Output is correct
12 Correct 49 ms 16256 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 12024 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 10 ms 12236 KB Output is correct
5 Correct 9 ms 12076 KB Output is correct
6 Correct 12 ms 12196 KB Output is correct
7 Correct 17 ms 12764 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 42 ms 15844 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 9 ms 12208 KB Output is correct
12 Correct 58 ms 16316 KB Output is correct
13 Correct 97 ms 18412 KB Output is correct
14 Correct 101 ms 18564 KB Output is correct
15 Correct 73 ms 18212 KB Output is correct
16 Correct 111 ms 18368 KB Output is correct
17 Correct 95 ms 18608 KB Output is correct
18 Correct 71 ms 18212 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 9 ms 12200 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 9 ms 12236 KB Output is correct
7 Correct 15 ms 12748 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 54 ms 15776 KB Output is correct
10 Correct 10 ms 12236 KB Output is correct
11 Correct 12 ms 12104 KB Output is correct
12 Correct 48 ms 16296 KB Output is correct
13 Correct 81 ms 18364 KB Output is correct
14 Correct 91 ms 18540 KB Output is correct
15 Correct 67 ms 18280 KB Output is correct
16 Correct 84 ms 18368 KB Output is correct
17 Correct 90 ms 18648 KB Output is correct
18 Correct 117 ms 18232 KB Output is correct
19 Execution timed out 543 ms 44728 KB Time limit exceeded
20 Halted 0 ms 0 KB -