Submission #129763

#	Time	Username	Problem	Language	Result	Execution time	Memory
129763		Vardanyan	Senior Postmen (BOI14_postmen)	C++14	55 / 100	1036 ms	133540 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+5;
vector<int> g[N];
vector<int> hv[N];
vector<int> pos[N];
vector<int> ans;
int st;
bool col[N];
vector<vector<int> > all;
int POS[N];
void dfs (int v, int p = -1) {
	//printf("%d!\n", v);
	if (col[v]) {
		st = v;
		//ans.clear();
		ans.push_back(v);
		return;
	}
		col[v] = 1;
//		set<int>::iterator it = g[v].begin();
		for(int i = POS[v];i<g[v].size();i++){
			int to = g[v][i];
			if (to != p && hv[v][i]) {
				dfs(to, v);
			//	g[v].erase(g[v].find(to));
				//g[to].erase(g[to].find(v));
				//mp[v][to] = mp[to][v] = 0;
				hv[v][i] = 0;
				hv[to][pos[v][i]] = 0;
				POS[v]++;
				if (v != st) {
					ans.push_back(v);
					break;
				}
				else {
					all.push_back(ans);
					ans.clear();
					//return;
				}
			}
		}
        col[v] = 0;
}

int main(){
   // ios_base::sync_with_stdio(false);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
        //mp[x][y] = 1;
       // mp[y][x] = 1;
        hv[x].push_back(1);
        hv[y].push_back(1);
        pos[x].push_back(g[y].size()-1);
        pos[y].push_back(g[x].size()-1);
    }
   // cout<<endl;
   vector<int> v;
   for(int i = 1;i<=n;i++) v.push_back(i);
  // random_shuffle(v.begin(),v.end());
    for(int j = 0;j<n;j++){
        int i = v[j];
        /*if(i == 2){
            cout<<0<<endl;
        }*/
       /* num++;
        now.clear();
        ans.clear();
        now.push_back(i);*/
        dfs(i);
        /*if(!ans.size()) continue;
        for(int i = 0;i<ans.size()-1;i++){
            cout<<ans[i]<<" ";
            int x = ans[i];
            int y = ans[i+1];
            g[x].erase(g[x].find(y));
            g[y].erase(g[y].find(x));
        }*/
       // cout<<endl;
    }
    for(int i = 0;i<all.size();i++){
        if(!all[i].size()) continue;
        for(int j = 0;j<all[i].size();j++) printf("%d ",all[i][j]);
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(int, int)':
postmen.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = POS[v];i<g[v].size();i++){
                      ~^~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<all.size();i++){
                   ~^~~~~~~~~~~
postmen.cpp:88:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<all[i].size();j++) printf("%d ",all[i][j]);
                       ~^~~~~~~~~~~~~~
postmen.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
postmen.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

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