Submission #2115726


Source Code Expand

#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

namespace CD { //centroid decomposition

	struct edge { int to, length; };

	vector<edge> G[MAX_N];
	bool centroid[MAX_N];
	int subtree_size[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
	}
	void add_edge(int a, int b, int c) {
		G[a].push_back((edge){b, c});
		G[b].push_back((edge){a, c});
	}

	int compute_subtree_size(int v, int p) {
		int c = 1;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			c += compute_subtree_size(G[v][i].to, v);
		}
		subtree_size[v] = c;
		return c;
	}

	pi search_centroid(int v, int p, int t) { 
		pi res = pi(inf, -1);
		int s = 1, m = 0;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;

			MIN(res, search_centroid(w, v, t));

			MAX(m, subtree_size[w]);
			s += subtree_size[w];
		}
		MAX(m, t - s);
		MIN(res, pi(m, v));
		return res;
	}


	void solve_subproblem(int v) {
		compute_subtree_size(v, -1);
		int cen = search_centroid(v, -1, subtree_size[v]).sec;
		centroid[cen] = true;

		set<pi> s;

		rep(i, 0, (int)G[cen].size()) {
			int n = G[cen][i].to;
			if(centroid[n]) continue;
			s.insert(pi(subtree_size[n], n));
		}

		while(sz(s) >= 2) {
			auto p1 = (*s.begin()); s.erase(p1);
			auto p2 = (*s.begin()); s.erase(p2);
			int a = p1.sec, b = p2.sec;
			int c;
			cout << "? " << a + 1 << " " << b + 1 << flush;
			cin >> c;
			if(c == a + 1) {
				solve_subproblem(a);
				return;
			}
			else if(c == b + 1){
				solve_subproblem(b);
				return;
			}
		}
		if(sz(s) == 1) {
			auto p1 = (*s.begin());
			int a = p1.sec, b = cen;
			int c;
			cout << "? " << a + 1 << " " << b + 1 << flush;
			cin >> c;
			if(c == a + 1) {
				solve_subproblem(a);
				return;
			}
		}
		cout << "! " << cen + 1 << flush;
		return;

		centroid[cen] = false;
	}
}

int N, Q;

void solve() {
	cin >> N >> Q;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		CD::add_edge(a, b, 1);
	}
	CD::solve_subproblem(0);
}

int main() {
#ifndef LOCAL
	// ios::sync_with_stdio(false);
 //    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    // freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Submission Info

Submission Time
Task E - ニワンゴくんの家探し
User omochana2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3985 Byte
Status TLE
Exec Time 2656 ms
Memory 5968 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 400 0 / 600
Status
TLE × 1
TLE × 10
TLE × 55
Set Name Test Cases
Sample 00_example_01.txt
Subtask1 s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt, s08.txt, s09.txt, s10.txt
All 00_example_01.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt, s08.txt, s09.txt, s10.txt
Case Name Status Exec Time Memory
00_example_01.txt TLE 2655 ms 5456 KB
01.txt TLE 2655 ms 5588 KB
02.txt TLE 2655 ms 5588 KB
03.txt TLE 2655 ms 5584 KB
04.txt TLE 2656 ms 5584 KB
05.txt TLE 2656 ms 5712 KB
06.txt TLE 2656 ms 5588 KB
07.txt TLE 2656 ms 5588 KB
08.txt TLE 2655 ms 5716 KB
09.txt TLE 2656 ms 5716 KB
10.txt TLE 2656 ms 5584 KB
11.txt TLE 2656 ms 5584 KB
12.txt TLE 2656 ms 5708 KB
13.txt TLE 2655 ms 5584 KB
14.txt TLE 2656 ms 5588 KB
15.txt TLE 2656 ms 5712 KB
16.txt TLE 2655 ms 5584 KB
17.txt TLE 2656 ms 5584 KB
18.txt TLE 2656 ms 5588 KB
19.txt TLE 2656 ms 5584 KB
20.txt TLE 2656 ms 5584 KB
21.txt TLE 2656 ms 5584 KB
22.txt TLE 2656 ms 5584 KB
23.txt TLE 2656 ms 5460 KB
24.txt TLE 2656 ms 5588 KB
25.txt TLE 2656 ms 5584 KB
26.txt TLE 2656 ms 5584 KB
27.txt TLE 2656 ms 5584 KB
28.txt TLE 2656 ms 5580 KB
29.txt TLE 2656 ms 5584 KB
30.txt TLE 2656 ms 5580 KB
31.txt TLE 2656 ms 5584 KB
32.txt TLE 2656 ms 5584 KB
33.txt TLE 2656 ms 5588 KB
34.txt TLE 2656 ms 5588 KB
35.txt TLE 2656 ms 5460 KB
36.txt TLE 2656 ms 5584 KB
37.txt TLE 2656 ms 5584 KB
38.txt TLE 2656 ms 5584 KB
39.txt TLE 2656 ms 5584 KB
40.txt TLE 2656 ms 5588 KB
41.txt TLE 2656 ms 5584 KB
42.txt TLE 2656 ms 5584 KB
43.txt TLE 2655 ms 5584 KB
44.txt TLE 2655 ms 5712 KB
s01.txt TLE 2655 ms 5836 KB
s02.txt TLE 2656 ms 5844 KB
s03.txt TLE 2655 ms 5968 KB
s04.txt TLE 2655 ms 5840 KB
s05.txt TLE 2656 ms 5712 KB
s06.txt TLE 2656 ms 5840 KB
s07.txt TLE 2656 ms 5580 KB
s08.txt TLE 2656 ms 5712 KB
s09.txt TLE 2655 ms 5456 KB
s10.txt TLE 2655 ms 5452 KB