Submission #2018464


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define PB push_back
#define MP make_pair

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MOD = 1e9+7;
const int INF = 1e9;
const int MAX_N = 20;

int N, Q, a, b;
vvi edges(MAX_N);
bool used[MAX_N];
int n_subs[MAX_N][5];

int sum_ch(int x) {
  int res = 1;
  if (used[x] || edges[x].empty()) return res;
  for (int i = 0; i < N; i++) {
    n_subs[x][i] = 0;
  }
  used[x] = true;

  int idx;
  for (int i = 0; i < edges[x].size(); i++) {
    if (used[edges[x][i]]) {
      idx = i;
      continue;
    }
    n_subs[x][i] = sum_ch(edges[x][i]);
    res += n_subs[x][i];
  }
  n_subs[x][idx] = N - res;

  used[x] = false;
  return res;
}

void er_dfs(int id) {
  if (used[id]) return;
  used[id] = true;
  for (vi::iterator it=edges[id].begin(); it!=edges[id].end(); ++it) {
    er_dfs(*it);
  }
  edges[id].clear();
  used[id] = false;
}

int main() {
  cin >> N >> Q;
  for (int i = 0; i < N-1; i++) {
    cin >> a >> b; a--; b--;
    edges[a].PB(b);
    edges[b].PB(a);
    used[i] = false;
  }
  // sum_ch(0);
  // for (int i = 0; i < N; i++) {
  //   for (int j = 0; j < edges[i].size(); j++) {
  //     cout << n_subs[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  int cal_id = 0, x, rest_ch = N;
  bool loop_flag = true;
  while (loop_flag) {
    // cout << "rest = " << rest_ch << endl;
    // for (int i = 0; i < N; i++) {
    //   cout << edges[i].size() << endl;
    // }
    sum_ch(cal_id);

    int mnd = cal_id, smnd, cent = -1, mi, smi;
    for (int i = 0; i < N; i++) {
      if (edges[i].empty()) continue;
      bool flag = true;
      int mx = -1, smx = -1;
      for (int j = 0; j < edges[i].size(); j++) {
        if (N/2 < n_subs[i][j]) {
          flag = false;
          break;
        }
        if (mx < n_subs[i][j]) {
          smx = mx;
          mx = n_subs[i][j];
          smnd = mnd;
          smi = mi;
          mnd = edges[i][j];
          mi = j;
        } else if (smx < n_subs[i][j]) {
          smx = n_subs[i][j];
          smi = j;
          smnd = edges[i][j];
        }
      }
      if (flag) {
        cent = i;
        break;
      }
    }
    cout << "? " << (mnd+1) << " " << (smnd+1) << endl;
    cin >> x;
    if (rest_ch <= 2) {
      cout << "! " << x << endl;
      loop_flag = false;
    } else {
      if (x == 0) {
        cal_id = cent;

        used[cent] = true;
        er_dfs(mnd);
        er_dfs(smnd);
        used[cent] = false;

        edges[cent].erase(find(edges[cent].begin(), edges[cent].end(), mnd));
        edges[cent].erase(find(edges[cent].begin(), edges[cent].end(), smnd));

        rest_ch = rest_ch - n_subs[cal_id][mi] - n_subs[cal_id][smi];
      } else {
        cal_id = x-1;
        
        used[cal_id] = true;
        er_dfs(cent);
        used[cal_id] = false;

        edges[cal_id].erase(find(edges[cal_id].begin(), edges[cal_id].end(), cent));

        rest_ch = n_subs[cent][(cal_id==mnd)?mi:smi];
      }
    }
  }

  return 0;
}

Submission Info

Submission Time
Task E - ニワンゴくんの家探し
User mon10
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3261 Byte
Status
Exec Time 102 ms
Memory 3028 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt
Subtask1 0 / 400 s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt, s08.txt, s09.txt, s10.txt
All 0 / 600 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 98 ms 720 KB
01.txt 99 ms 852 KB
02.txt 99 ms 848 KB
03.txt 101 ms 3028 KB
04.txt 99 ms 976 KB
05.txt 100 ms 980 KB
06.txt 98 ms 848 KB
07.txt 99 ms 848 KB
08.txt 100 ms 848 KB
09.txt 100 ms 3024 KB
10.txt 99 ms 976 KB
11.txt 99 ms 848 KB
12.txt 99 ms 976 KB
13.txt 100 ms 976 KB
14.txt 99 ms 848 KB
15.txt 99 ms 848 KB
16.txt 100 ms 976 KB
17.txt 99 ms 852 KB
18.txt 99 ms 848 KB
19.txt 100 ms 848 KB
20.txt 98 ms 844 KB
21.txt 99 ms 848 KB
22.txt 99 ms 848 KB
23.txt 102 ms 844 KB
24.txt 100 ms 852 KB
25.txt 100 ms 848 KB
26.txt 100 ms 976 KB
27.txt 101 ms 852 KB
28.txt 101 ms 852 KB
29.txt 101 ms 848 KB
30.txt 99 ms 848 KB
31.txt 101 ms 848 KB
32.txt 102 ms 976 KB
33.txt 100 ms 848 KB
34.txt 100 ms 848 KB
35.txt 101 ms 848 KB
36.txt 101 ms 848 KB
37.txt 99 ms 848 KB
38.txt 99 ms 844 KB
39.txt 98 ms 848 KB
40.txt 100 ms 848 KB
41.txt 99 ms 844 KB
42.txt 100 ms 976 KB
43.txt 100 ms 976 KB
44.txt 101 ms 976 KB
s01.txt 99 ms 848 KB
s02.txt 100 ms 1104 KB
s03.txt 100 ms 972 KB
s04.txt 99 ms 976 KB
s05.txt 99 ms 976 KB
s06.txt 100 ms 848 KB
s07.txt 99 ms 848 KB
s08.txt 100 ms 848 KB
s09.txt 99 ms 720 KB
s10.txt 98 ms 720 KB