Submission #291852

#	Time	Username	Problem	Language	Result	Execution time	Memory
291852		Blagojce	Senior Postmen (BOI14_postmen)	C++11	55 / 100	599 ms	76028 KiB

postmen

#include <bits/stdc++.h>
#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 = 6*1e5;

int n, m;
vector<int> g[mxn];
bool used[mxn];
int l[mxn], r[mxn];

vector<int> cycle;

int nxt(int u, int edge){
	return l[edge]^r[edge]^u;
}
void euler(int u){
	fr(i, 0, (int)g[u].size()){
		if(used[g[u][i]]){
			swap(g[u][i], g[u].back());
			g[u].pop_back();
			--i;
			continue;
		}
		used[g[u][i]] = true;
		euler(nxt(u, g[u][i]));
	}
	cycle.pb(u);
	
}
vector<int> sol[mxn];
int R[mxn];

int _next[mxn];
int lst[mxn];

void restore(){
	memset(lst, -1, sizeof(lst));
	
	for(int i = cycle.size()-1; i >= 0; i --){
		_next[i] = lst[cycle[i]];
		lst[cycle[i]] = i;	
	}
	
	sol[0].pb(0);
	R[0] = _next[0];
	stack<int> S;
	S.push(0);
	int id = 1;
	fr(i, 1, (int)cycle.size()-1){
		int u = cycle[i];
		if(R[S.top()] == i) S.pop();
		if(S.empty() || (_next[i] != -1 && _next[i] <= R[S.top()])){
			S.push(id);
			sol[id].pb(u);
			R[id] = _next[i];
			id++;
		}
		else{
			sol[S.top()].pb(u);
		}
	}
	fr(i, 0, id+1){
		for(auto u : sol[i]) printf("%d ", u+1);
		printf("\n");
	}
	
}

void solve(){
	scanf("%d %d", &n, &m);
	fr(i, 0, m){
		scanf("%d %d", &l[i], &r[i]);
		--l[i], --r[i];
		g[l[i]].pb(i);
		g[r[i]].pb(i);
	}
	euler(0);

	restore();
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Compilation message (stderr)

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

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