Submission #1101696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101696		PagodePaiva	Senior Postmen (BOI14_postmen)	C++17	100 / 100	484 ms	71112 KiB

postmen

#include<bits/stdc++.h>

using namespace std;

const int N = 500010;
vector <pair <int, int>> g[N];
int mark[N];
vector <int> path;

void dfs(int v){
    while(!g[v].empty()){
        auto [x, idx] = g[v].back();
        g[v].pop_back();
        if(mark[idx]) continue;
        mark[idx] = 1;
        dfs(x);
    }
    path.push_back(v);
}

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i <m;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    dfs(1);
    memset(mark, 0, sizeof mark);
    vector <vector <int>> v;
    stack <int> at;
    for(int i = 0;i < path.size();i++){
        if(mark[path[i]] == 0) {
            mark[path[i]] = 1;
            at.push(path[i]);
        }
        else{
            vector <int> aux;
            aux.push_back(path[i]);
            while(!at.empty()){
                if(at.top() == path[i]) break;
                aux.push_back(at.top());
                mark[at.top()] = 0;
                at.pop();
            }
            aux.push_back(path[i]);
            v.push_back(aux);
        }
    }
    for(auto vv : v){
       for(int i = 0;i < vv.size()-1;i++){
            cout << vv[i] << ' ';
       }
        cout << '\n';
    }
}

Compilation message (stderr)

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45