Submission #722677

#	Time	Username	Problem	Language	Result	Execution time	Memory
722677		mnbvcxz123	Senior Postmen (BOI14_postmen)	C++17	100 / 100	439 ms	97612 KiB

postmen

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ar=array<int,2>;
constexpr int MAXN=5e5+1;
int n,m,nxt[MAXN],cyc;
bool vis[MAXN],trav[MAXN];
vector<ar>g[MAXN];
vector<int>res;

void dfs(int v){
        vis[v]=1;
        while(nxt[v]<g[v].size()){
                auto i=g[v][nxt[v]++];
                if(!trav[i[1]]){
                        trav[i[1]]=1;
                        if(vis[i[0]]){
                                res.push_back(v);
                                cyc=i[0];
                                return;
                        }
                        dfs(i[0]);
                        res.push_back(v);
                        if(cyc==v){
                                for(const int&i:res){
                                        cout<<i<<' ';
                                        vis[i]=0;
                                }
                                res.clear();
                                cout<<'\n';
                                cyc=0;
                                vis[v]=1;
                        }
                        else if(cyc)return;
                }
        }
}

int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int n,m;
        cin>>n>>m;
        for(int i=0,a,b;i<m;++i){
                cin>>a>>b;
                g[a].push_back({b,i});
                g[b].push_back({a,i});
        }
        for(int i=1;i<=n;++i)
                if(nxt[i]<g[i].size())dfs(i);
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         while(nxt[v]<g[v].size()){
      |               ~~~~~~^~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 if(nxt[i]<g[i].size())dfs(i);
      |                    ~~~~~~^~~~~~~~~~~~

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