Submission #715011

#	Time	Username	Problem	Language	Result	Execution time	Memory
715011		Ahmed57	Senior Postmen (BOI14_postmen)	C++14	0 / 100	8 ms	11988 KiB

postmen

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

using namespace std;
const int MOD = 1e9 + 7;
const int BUF_SZ = 1 << 15;
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (int)fread(buf, 1, BUF_SZ, stdin);
		if (!len) {
			return EOF;
		}
	}
	return buf[pos++];
}

int read_int() {
	int x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') {
			sgn *= -1;
		}
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) {
		x = x * 10 + (ch - '0');
	}
	return x * sgn;
}
} // namespace Input
inline namespace Output {
char buf[BUF_SZ];
int pos;

void flush_out() {
	fwrite(buf, 1, pos, stdout);
	pos = 0;
}

void write_char(char c) {
	if (pos == BUF_SZ) {
		flush_out();
	}
	buf[pos++] = c;
}

void write_int(int x) {
	static char num_buf[100];
	if (x < 0) {
		write_char('-');
		x *= -1;
	}
	int len = 0;
	for (; x >= 10; x /= 10) {
		num_buf[len++] = (char)('0' + (x % 10));
	}
	write_char((char)('0' + x));
	while (len) {
		write_char(num_buf[--len]);
	}
	write_char('\n');
}

// auto-flush output when program exits
void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output

int vised[500001];
int vis[500001];
vector<pair<int,int>>adj[500001];
stack<int> s;
vector<vector<int>> all;
int str= 0;
void dfs(int i){
    s.push(i);
    if(vis[i]){
        vector<int>a;a.push_back(s.top());
        s.pop();
        while(s.top()!=i){
            a.push_back(s.top());
            s.pop();
        }
        all.push_back(a);
        str = a.size()-1;
        return;
    }
    vis[i] =1;
    for(auto j:adj[i]){
        if(vised[j.second])continue;
        vised[j.second] = 1;
        dfs(j.first);
        if(str){
            vis[i] =0;
            str--;
            return ;
        }
    }
    vis[i] = 0;
    if(s.size())s.pop();
}
signed main(){
    init_output();
    int n = read_int(),m=read_int();
    for(int i = 0;i<m;i++){
        int a=read_int(),b=read_int();
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    for(int i = 1;i<=n;i++){
        dfs(i);
    }
    for(auto i:all){
        for(auto j:i){write_int(j);write_char(' ');}
        write_char('\n');
    }
    return 0;
}

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