Submission #413925

#	Time	Username	Problem	Language	Result	Execution time	Memory
413925		Blagojce	Senior Postmen (BOI14_postmen)	C++11	55 / 100	522 ms	48636 KiB

postmen

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5*1e5+5;
 
int n, m;
vector<int> g[mxn];
int deg[mxn];
bool used[mxn];
int l[mxn], r[mxn];
 
vector<int> cycle;
/*
void euler(int u, int dep){
	cout<<dep<<endl;
	
	while(deg[u] > 0){
		cout<<"a";
		int e = g[u][deg[u]-1];
		cout<<"b";
		int v = l[e];
		cout<<"v";
		if(v == u) v = r[e];
		--deg[u];
		cout<<"g";
		
		cout<<e<<endl;
		if(used[e]) continue;
		used[e] = true;
		cout<<"BEFORE"<<endl;
		euler(v, dep+1);
	}
	
	cycle.pb(u);
}
*/
stack<int> S;
void eul(){
	S.push(0);
	while(!S.empty()){
		int u = S.top();
		if(deg[u] > 0){
			int e = g[u][deg[u]-1];
			int v = l[e];
			if(v == u) v = r[e];
			--deg[u];
			if(used[e]) continue;
			used[e] = true;
			S.push(v);
		}
		else{
			cycle.pb(u);
			S.pop();
		}
	}
}

bool vis[mxn];
 
int main(){
	//freopen("untitled.in", "r",stdin);
	scanf("%d %d", &n, &m);
	fr(i, 0, m){
		scanf("%d %d", &l[i], &r[i]);
		--l[i], --r[i];
		++deg[l[i]];
		++deg[r[i]];
		g[l[i]].pb(i);
		g[r[i]].pb(i);
	}
	
	//euler(0, 0);
	eul();
	stack<int> S;
	for(auto u : cycle){
		if(vis[u]){
			while(1){
				int x = S.top();
				printf("%d ", x+1);
				S.pop();
				vis[x] = false;
				if(x == u){
					printf("\n");
					break;
				}
			}
		}
		vis[u] = true;
		S.push(u);
	}
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d %d", &l[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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