oj.uz

Submission #755470

# Submission time Handle Problem Language Result Execution time Memory
755470 2023-06-10T07:01:27 Z irmuun Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 108384 KB 
#include<bits/stdc++.h>

using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    set<int>adj[n+1];
    vector<int>used(n+1,0);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    vector<int>ord;
    function <void(int)> dfs=[&](int x){
        ord.pb(x);
        if(adj[x].size()==0){
            return;
        }
        int y=*adj[x].begin();
        adj[x].erase(y);
        adj[y].erase(x);
        dfs(y);
    };
    for(int i=1;i<=n;i++){
        if(adj[i].size()>0){
            dfs(i);
        }
    }
    vector<int>v;
    for(int i=0;i<ord.size();i++){
        if(used[ord[i]]==0){
            used[ord[i]]=1;
            v.pb(ord[i]);
        }
        else{
            int x=ord[i];
            cout<<x<<' ';
            while(!v.empty()){
                int y=v.back();
                if(x!=y){
                    cout<<y<<' ';
                    v.pop_back();
                    used[y]=0;
                }
                else{
                    break;
                }
            }
            cout<<"\n";
        }
    }
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<ord.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
38.0 / 38.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 1 ms 320 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 12 ms 2312 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 137 ms 11340 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 140 ms 11624 KB Output is correct

Subtask #2
17.0 / 17.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 1 ms 320 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 5 ms 892 KB Output is correct
7 Correct 15 ms 2260 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 131 ms 11280 KB Output is correct
10 Correct 2 ms 840 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 120 ms 11676 KB Output is correct
13 Correct 80 ms 21632 KB Output is correct
14 Correct 119 ms 20468 KB Output is correct
15 Correct 99 ms 19636 KB Output is correct
16 Correct 101 ms 21796 KB Output is correct
17 Correct 108 ms 19928 KB Output is correct
18 Correct 96 ms 16948 KB Output is correct

Subtask #3
0 / 45.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 1 ms 212 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 868 KB Output is correct
7 Correct 11 ms 2260 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 110 ms 11328 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 2 ms 712 KB Output is correct
12 Correct 106 ms 11620 KB Output is correct
13 Correct 77 ms 21660 KB Output is correct
14 Correct 107 ms 20444 KB Output is correct
15 Correct 81 ms 19656 KB Output is correct
16 Correct 74 ms 21628 KB Output is correct
17 Correct 113 ms 20020 KB Output is correct
18 Correct 97 ms 16948 KB Output is correct
19 Execution timed out 511 ms 108384 KB Time limit exceeded
20 Halted 0 ms 0 KB -