Submission #115989

#	Time	Username	Problem	Language	Result	Execution time	Memory
115989		ckodser	Senior Postmen (BOI14_postmen)	C++14	100 / 100	427 ms	47928 KiB

postmen

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=5e5+500;
const ll inf=1e9+900;

vector<ll> ger[maxn];
ll nex[2*maxn];
ll yal[2*maxn];
ll head[maxn];
ll cnt=0;

ll s[maxn];
ll t[maxn];
bool vis[maxn];
stack<ll> ans;
bool inAns[maxn];


void dfs(ll a){
    while(head[a]!=-1){
	ll e=yal[head[a]];
	head[a]=nex[head[a]];
	if(!vis[e]){
	    vis[e]=1;
	    dfs(s[e]^t[e]^a);
	}
    }
    if(inAns[a]){
	while(ans.top()!=a){
	    printf("%d ",ans.top());
	    inAns[ans.top()]=0;
	    ans.pop();
	}
	printf("%d\n",a);
    }else{
        ans.push(a);
	inAns[a]=1;
    }
}
int main(){
    ll n,m;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof head);
    for(ll i=0;i<m;i++){
	scanf("%d%d",&s[i],&t[i]);
	nex[cnt]=head[s[i]];
	head[s[i]]=cnt;
	yal[cnt]=i;
	cnt++;

	nex[cnt]=head[t[i]];
	head[t[i]]=cnt;
	yal[cnt]=i;
	cnt++;
    }
    dfs(1);
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
postmen.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&s[i],&t[i]);
  ~~~~~^~~~~~~~~~~~~~~~~~~~

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