Submission #941115

#	Time	Username	Problem	Language	Result	Execution time	Memory
941115		Ghulam_Junaid	Senior Postmen (BOI14_postmen)	C++17	55 / 100	601 ms	125628 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 10;
int n, m, ind[N];
set<int> g[N];
bool vis[N];
 
vector<int> path;
int dfs(int v, int prev = -1){
    // cout << "dfs on " << v << endl;
    vis[v] = 1;
    ind[v] = path.size();
    path.push_back(v);
 
    while (!g[v].empty()){
        int u = *g[v].begin();
        g[v].erase(u);
        g[u].erase(v);
        if (prev == u) continue;
        if (!vis[u]){
            int found = dfs(u, v);
            // cout << "I am " << v << " cycle found is at " << found << " neighbour was " << u << endl; 
            if (found != v){
                path.pop_back();
                vis[v] = 0;
                return found;
            }
        }
        else{
            for (int i = ind[u]; i < path.size(); i ++)
                printf("%d ", path[i]);
            printf("\n");
 
            // cout << "at v = " << v << " I found a cycle starting from " << u << endl; 
 
            path.pop_back();
            vis[v] = 0;
            return u;
        }
    }
    path.pop_back();
    return prev;
}
 
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++){
        int u, v;
        scanf("%d%d", &u, &v);
 
        g[u].insert(v);
        g[v].insert(u);
    }
 
    for (int i = 1; i <= n; i ++)
        if (!g[i].empty())
            dfs(i);
}

Compilation message (stderr)

postmen.cpp: In function 'int dfs(int, int)':
postmen.cpp:31:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for (int i = ind[u]; i < path.size(); i ++)
      |                                  ~~^~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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