oj.uz

Submission #733344

# Submission time Handle Problem Language Result Execution time Memory
733344 2023-04-30T14:07:43 Z Trunkty Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 223468 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,m;
vector<int> roads[500005];
int poi[500005];
unordered_map<int,bool> mp[500005];
bool vis[500005];
vector<int> curr;
vector<vector<int>> ans;

void euler(int x){
    if(vis[x]){
        curr = {x};
        return;
    }
    vis[x] = true;
    while(roads[x].size()!=poi[x]){
        int p = roads[x][poi[x]];
        poi[x]++;
        if(mp[x][p]){
            continue;
        }
        mp[p][x] = true;
        euler(p);
        if(curr.size()>0 and curr[0]!=x){
            curr.push_back(x);
            vis[x] = false;
            return;
        }
        else if(curr[0]==x){
            ans.push_back(curr);
            curr.clear();
        }
    }
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        roads[a].push_back(b);
        roads[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(roads[i].size()>0){
            euler(i);
        }
    }
    for(vector<int> i:ans){
        for(int j:i){
            cout << j << " ";
        }
        cout << "\n";
    }
	return 0;
}

Compilation message

postmen.cpp: In function 'void euler(ll)':
postmen.cpp:20:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   20 |     while(roads[x].size()!=poi[x]){
      |           ~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 21 ms 39364 KB Output is correct
3 Correct 21 ms 39472 KB Output is correct
4 Correct 23 ms 40048 KB Output is correct
5 Correct 23 ms 39508 KB Output is correct
6 Correct 25 ms 40140 KB Output is correct
7 Correct 31 ms 41428 KB Output is correct
8 Correct 23 ms 40148 KB Output is correct
9 Correct 88 ms 50724 KB Output is correct
10 Correct 23 ms 39984 KB Output is correct
11 Correct 24 ms 40020 KB Output is correct
12 Correct 96 ms 51320 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39380 KB Output is correct
2 Correct 22 ms 39380 KB Output is correct
3 Correct 24 ms 39420 KB Output is correct
4 Correct 26 ms 40064 KB Output is correct
5 Correct 25 ms 39508 KB Output is correct
6 Correct 27 ms 40044 KB Output is correct
7 Correct 45 ms 41416 KB Output is correct
8 Correct 26 ms 40128 KB Output is correct
9 Correct 93 ms 50764 KB Output is correct
10 Correct 26 ms 40056 KB Output is correct
11 Correct 26 ms 40020 KB Output is correct
12 Correct 90 ms 51276 KB Output is correct
13 Correct 112 ms 76284 KB Output is correct
14 Correct 98 ms 59644 KB Output is correct
15 Correct 123 ms 59240 KB Output is correct
16 Correct 110 ms 76236 KB Output is correct
17 Correct 123 ms 58816 KB Output is correct
18 Correct 114 ms 62976 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 22 ms 39368 KB Output is correct
3 Correct 24 ms 39424 KB Output is correct
4 Correct 24 ms 40020 KB Output is correct
5 Correct 24 ms 39508 KB Output is correct
6 Correct 24 ms 40032 KB Output is correct
7 Correct 32 ms 41448 KB Output is correct
8 Correct 24 ms 40148 KB Output is correct
9 Correct 96 ms 50792 KB Output is correct
10 Correct 32 ms 40020 KB Output is correct
11 Correct 33 ms 40020 KB Output is correct
12 Correct 83 ms 51336 KB Output is correct
13 Correct 109 ms 76232 KB Output is correct
14 Correct 105 ms 59696 KB Output is correct
15 Correct 122 ms 59200 KB Output is correct
16 Correct 114 ms 76312 KB Output is correct
17 Correct 132 ms 58816 KB Output is correct
18 Correct 135 ms 63044 KB Output is correct
19 Execution timed out 660 ms 223468 KB Time limit exceeded
20 Halted 0 ms 0 KB -