QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#690833 | #4926. Where Is the Root? | Mher777 | 0 | 3ms | 3912kb | C++20 | 5.5kb | 2024-10-31 05:14:09 | 2024-10-31 05:14:10 |
answer
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(time(nullptr));
/* -------------------- Typedefs -------------------- */
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
/* -------------------- Usings -------------------- */
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
/* -------------------- Defines -------------------- */
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);
/* -------------------- Constants -------------------- */
const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);
/* -------------------- Functions -------------------- */
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void precision(int x) {
cout.setf(ios::fixed | ios::showpoint);
cout.precision(x);
}
ll gcd(ll a, ll b) {
if (a == 0 || b == 0) return(max(a, b));
while (b) {
a %= b;
swap(a, b);
}
return a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
ll range_sum(ll a, ll b) {
if (a > b) return 0ll;
ll dif = a - 1, cnt = b - a + 1;
ll ans = ((b - a + 1) * (b - a + 2)) / 2;
ans += ((b - a + 1) * dif);
return ans;
}
string dec_to_bin(ll a) {
string s = "";
for (ll i = a; i > 0; ) {
ll k = i % 2;
i /= 2;
char c = k + 48;
s += c;
}
if (a == 0) {
s = "0";
}
reverse(all(s));
return s;
}
ll bin_to_dec(string s) {
ll num = 0;
for (int i = 0; i < s.size(); i++) {
num *= 2ll;
num += (s[i] - '0');
}
return num;
}
ll factorial_by_mod(ll n, ll mod) {
ll ans = 1;
ll num;
for (ll i = 1; i <= n; ++i) {
num = i % mod;
ans *= num;
ans %= mod;
}
return ans;
}
bool isPrime(ll a) {
if (a == 1) return false;
for (ll i = 2; i * i <= a; i++) {
if (a % i == 0) return false;
}
return true;
}
ll binpow(ll a, ll b) {
if (!a) return 0;
ll ans = 1;
while (b) {
if (b & 1) {
ans *= a;
}
b >>= 1;
a *= a;
}
return ans;
}
ll binpow_by_mod(ll a, ll b, ll mod) {
if (!a) return 0;
ll ans = 1;
while (b) {
if (b & 1) {
ans *= a;
ans %= mod;
}
b >>= 1;
a *= a;
a %= mod;
}
return ans;
}
/* -------------------- Solution -------------------- */
const int N = 505;
int used[N];
vi g[N];
int dfs(int u, int par) {
int sz = 1;
for (auto to : g[u]) {
if (to == par) continue;
sz += dfs(to, u);
}
return sz;
}
bool qry(vi vec) {
if ((int)vec.size() == 0) return false;
cout << "? " << (int)vec.size() << " ";
for (auto elem : vec) {
cout << elem << " ";
}
cout << endl;
string s;
cin >> s;
if (s == "YES") return true;
return false;
}
void slv() {
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
g[x].pub(y);
g[y].pub(x);
}
int mn = MAX, u = 0;
for (int i = 1; i <= n; ++i) {
int sz = 0;
for (auto to : g[i]) {
sz = max(dfs(to, i), sz);
}
if (sz < mn) {
mn = sz;
u = i;
}
}
while (1) {
vi v;
used[u] = 1;
for (auto to : g[u]) {
if (used[to]) continue;
v.pub(to);
}
if (!qry(v)) {
cout << "! " << u << endl;
return;
}
int l = 0, r = (int)v.size() - 1, mid;
vi vec;
while ((r - l + 1) > 2) {
mid = (l + r) / 2;
vec.clear();
for (int i = 0; i <= mid; ++i) {
vec.pub(v[i]);
}
if (qry(vec)) {
r = mid;
}
else {
l = mid + 1;
}
}
if (l == r) {
u = v[l];
}
else {
if (qry({ u,v[l],(l == 0 ? v.back() : v[0])})) {
u = v[l];
}
else {
u = v[r];
}
}
}
}
void cs() {
int tstc = 1;
//cin >> tstc;
while (tstc--) {
slv();
}
}
void precalc() {
return;
}
int main() {
fastio();
precalc();
//precision(0);
cs();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 1ms
memory: 3620kb
input:
7 4 1 1 2 4 3 3 5 3 6 4 7 NO
output:
? 3 1 3 7 ! 4
result:
ok OK
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3912kb
input:
9 5 9 8 6 2 8 1 8 3 6 6 7 1 4 4 5 YES YES YES NO
output:
? 3 6 2 1 ? 2 6 2 ? 3 8 6 1 ? 2 3 7 ! 6
result:
wrong output format Unexpected end of file - int32 expected
Subtask #2:
score: 0
Wrong Answer
Test #24:
score: 10
Accepted
time: 1ms
memory: 3912kb
input:
30 1 15 29 30 1 4 7 28 29 17 1 26 26 7 12 5 27 13 3 7 27 1 21 15 9 22 22 5 24 27 19 1 25 30 22 27 6 15 16 13 18 2 27 10 27 30 20 26 8 15 18 8 14 1 27 23 11 3 YES NO YES YES YES NO NO
output:
? 6 15 4 26 27 19 14 ? 3 15 4 26 ? 5 15 4 26 27 19 ? 3 1 27 15 ? 6 13 24 22 10 30 23 ? 3 13 24 22 ? 5 13 24 22 10 30 ! 23
result:
ok OK
Test #25:
score: 10
Accepted
time: 0ms
memory: 3692kb
input:
30 15 16 8 6 19 2 26 17 30 15 26 4 1 6 1 23 15 1 29 25 21 3 12 1 2 24 29 22 9 1 3 10 27 28 5 12 20 5 14 7 5 26 7 18 10 23 1 28 3 11 7 1 19 23 13 23 29 30 YES NO NO YES YES
output:
? 7 6 23 15 12 9 28 7 ? 4 6 23 15 12 ? 6 6 23 15 12 9 28 ? 2 14 18 ? 3 7 14 18 ! 14
result:
ok OK
Test #26:
score: 0
Wrong Answer
time: 0ms
memory: 3636kb
input:
30 19 7 14 27 22 18 15 19 1 18 27 23 21 28 19 24 25 10 27 3 23 7 9 26 20 4 7 9 12 19 6 19 23 17 18 5 5 8 21 25 10 30 9 1 5 29 2 7 12 10 11 6 4 10 26 13 5 16 YES NO YES YES YES YES
output:
? 4 19 23 9 2 ? 2 19 23 ? 3 7 9 19 ? 2 26 1 ? 3 9 26 1 ? 1 13 ! 13
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Wrong Answer
Test #54:
score: 0
Wrong Answer
time: 3ms
memory: 3692kb
input:
500 419 133 44 225 391 269 419 461 293 347 108 31 110 363 423 257 321 155 498 87 180 492 251 5 357 30 341 172 275 109 372 446 286 336 208 339 162 320 138 103 129 219 62 141 359 286 130 238 470 460 418 48 210 358 429 13 323 143 382 415 406 394 309 175 325 170 128 108 6 113 363 17 470 457 7 224 288 48...
output:
? 9 89 356 253 340 474 325 499 1 156 ? 5 89 356 253 340 474 ? 3 89 356 253 ? 2 89 356 ? 3 139 89 156 ? 8 21 363 263 475 295 45 171 84 ? 4 21 363 263 475 ? 6 21 363 263 475 295 45 ? 3 89 295 21 ? 3 147 124 431 ? 2 147 124 ? 3 295 147 431 ? 6 271 206 368 188 195 5 ? 3 271 206 368 ? 2 271...
result:
wrong output format Unexpected end of file - int32 expected