oj.uz

답안 #61534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61534 2018-07-26T07:15:06 Z DrumpfTheGodEmperor Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 4 ms 884 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define MOD 1000000007
#define INF 1061109567
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
const int N=515;
int sz[N],par[N];
vector<int> v,G[N];
void dfs(int u,int p,bool pushed) {
	sz[u]=1;
	fa (v,G[u]) if (v!=p) {
		dfs(v,u,pushed);
		par[v]=u;
		sz[u]+=sz[v];
	}
	if (pushed) v.pb(u);
}
int cen(int u,int p,int cur) {
	fa (v,G[u]) if (v!=p) {
		if (sz[v]*2>=cur) return cen(v,u,cur);
	}
	return u;
}
int ask(int u,int p) {
	v.clear();
	dfs(u,p,0);
	int tmp=cen(u,p,sz[u]);
	dfs(tmp,par[tmp],1);
	if (v.size()==1) return v[0];
	bool temp=query(v);
	if (tmp) return ask(tmp,par[tmp]);
	else return ask(par[tmp],tmp);
}
int findEgg(int n,vector<pair<int,int>> bridges) {
	fa (i,bridges) {
		i.fi--; i.se--;
		G[i.fi].pb(i.se);
		G[i.se].pb(i.fi);
	}
	/*
	Pick a centroid - like center for the tree. Now ask on its subtree. If the egg exists inside
	then go for it. Else, go back up to the center.
	*/
	cout<<ask(0,-1);
}

Compilation message

eastereggs.cpp: In function 'int ask(int, int)':
eastereggs.cpp:38:7: warning: unused variable 'temp' [-Wunused-variable]
  bool temp=query(v);
       ^~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -