제출 #715014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715014		Ahmed57	Senior Postmen (BOI14_postmen)	C++14	100 / 100	368 ms	87952 KiB

postmen

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

using namespace std;
int in(){
	char c=getchar_unlocked();
	while(c<'0'||c>'9')
		c=getchar_unlocked();
	int r=0;
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar_unlocked();
	}
	return r;
}

void out(int x) {
	int lz=0, r=0;
	while(x%10==0) {
		++lz;
		x/=10;
	}
	while(x) {
		r=r*10+x%10;
		x/=10;
	}
	while(r) {
		putchar_unlocked('0'+r%10);
		r/=10;
	}
	while(lz--)
		putchar_unlocked('0');
}

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(){
    int n = in();int m=in();
    for(int i = 0;i<m;i++){
        int a=in();int b=in();
        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){out(j);putchar_unlocked(' ');}
        putchar_unlocked('\n');
    }
    return 0;
}

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