Submission #197530

#	Time	Username	Problem	Language	Result	Execution time	Memory
197530		dndhk	Senior Postmen (BOI14_postmen)	C++14	55 / 100	791 ms	67416 KiB

postmen

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 500000;

int N, M;
vector<int> gp[MAX_N+1];
bool chk[MAX_N+1];
pii p[MAX_N+1];
vector<int> v;
vector<int> nxt[MAX_N+1];
bool vst[MAX_N+1];
vector<int> vt;

int main(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(i);
		gp[b].pb(i);
		p[i] = {a, b};
	}
	for(int i=1; i<=N; i++){
		for(int j=0; j<gp[i].size(); j+=2){
			nxt[gp[i][j]].pb(gp[i][j+1]);
			nxt[gp[i][j+1]].pb(gp[i][j]);
		}
	}
	for(int i=1; i<=M; i++){
		if(!chk[i]){
			chk[i] = true;
			chk[nxt[i][0]] = true;
			v.pb(nxt[i][0]);
			v.pb(i);
			int n = nxt[i][1];
			while(1){
				chk[n] = true;
				v.pb(n);
				if(chk[nxt[n][0]] && chk[nxt[n][1]]){
					break;
				}
				if(chk[nxt[n][0]]){
					n = nxt[n][1];
				}else{
					n = nxt[n][0];
				}
			}
			int x;
			if(p[v.back()].first==p[v[0]].first || p[v.back()].first==p[v[0]].second){
				x = p[v.back()].first;
			}else{
				x = p[v.back()].second;
			}
			vt.pb(x);
			vst[x] = true;
			while(!v.empty()){
				x = p[v.back()].first+p[v.back()].second-x;
				if(vst[x]){
					while(vt.back()!=x){
						vst[vt.back()] = false;
						printf("%d ", vt.back());
						vt.pop_back();
					}
					printf("%d\n", x);
				}else{
					vst[x] = true;
					vt.pb(x);
				}
				v.pop_back();
			}
			while(!vt.empty()){
				vst[vt.back()] = false;
				vt.pop_back();
			}
		}
	}
	return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[i].size(); j+=2){
                ~^~~~~~~~~~~~~
postmen.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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