QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690858#4926. Where Is the Root?Mher7770 1ms3856kbC++206.3kb2024-10-31 06:17:102024-10-31 06:17:11

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 06:17:11]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3856kb
  • [2024-10-31 06:17: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;
vi g[N], nodes;

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 make_it(int u, int par, int need, int dist = 0) {
    if (dist == need) {
        nodes.pub(u);
        return;
    }
    for (auto to : g[u]) {
        if (to == par) continue;
        make_it(to, u, need, dist + 1);
    }
}

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, gag = 0;
    for (int i = 1; i <= n; ++i) {
        if ((int)g[i].size() <= 2) continue;
        if ((int)g[i].size() < mn) {
            mn = (int)g[i].size();
            u = i;
        }
    }
    vi vec;
    for (auto to : g[u]) {
        vec.pub(to);
    }
    if (!qry(vec)) {
        cout << "! " << u << endl;
        return;
    }
    int l = 0, r = (int)vec.size() - 1, mid;
    vi cur_vec;
    while ((r - l + 1) > 2) {
        mid = (l + r) / 2;
        cur_vec.clear();
        for (int i = l; i <= mid; ++i) {
            cur_vec.pub(vec[i]);
        }
        if (qry(cur_vec)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    gag = u;
    if (l == r) {
        u = vec[l];
    }
    else {
        if (qry({ vec[l],(l == 0 ? vec.back() : vec[0]) })) {
            u = vec[l];
        }
        else {
            u = vec[r];
        }
    }
    l = 1, r = 500;
    int final_dist = 0;
    while (l <= r) {
        mid = (l + r) / 2;
        nodes.clear();
        make_it(u, u, mid);
        if (!qry(nodes)) {
            r = mid - 1;
        }
        else {
            final_dist = mid;
            l = mid + 1;
        }
    }
    if (final_dist == 0) {
        cout << "! " << u << endl;
        return;
    }
    vec.clear();
    l = 0, r = (int)nodes.size() - 1;
    while (l < r) {
        mid = (l + r) / 2;
        vec.clear();
        vec.pub(gag);
        for (int i = 0; i <= mid; ++i) {
            vec.pub(nodes[i]);
        }
        if (qry(vec)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << "! " << nodes[l] << endl;
    return;
}

void cs() {
    int tstc = 1;
    //cin >> tstc;
    while (tstc--) {
        slv();
    }
}

void precalc() {
    return;
}

int main() {
    fastio();
    precalc();
    //precision(0);
    cs();
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 0ms
memory: 3672kb

input:

7
4 1
1 2
4 3
3 5
3 6
4 7
YES
YES
YES
NO

output:

? 3 4 5 6 
? 2 4 5 
? 2 4 6 
? 3 1 3 7 
! 4

result:

ok OK

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3692kb

input:

9
5 9
8 6
2 8
1 8
3 6
6 7
1 4
4 5
YES
YES
YES
YES
YES

output:

? 3 8 3 7 
? 2 8 3 
? 2 8 7 
? 1 5 
? 1 9 
! 9

result:

wrong output format Unexpected end of file - int32 expected

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 0ms
memory: 3628kb

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
YES
NO
YES
NO
NO
NO
NO

output:

? 3 28 26 3 
? 2 28 26 
? 2 28 3 
? 10 21 6 8 13 24 22 10 30 23 11 
? 3 2 12 17 
? 6 18 16 9 5 29 25 
? 4 7 18 16 9 
? 6 7 18 16 9 5 29 
! 25

result:

wrong output format Unexpected end of file - int32 expected

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 59
Acceptable Answer
time: 0ms
memory: 3856kb

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:

? 3 193 378 143 
? 2 193 378 
? 77 155 28 380 476 73 132 331 291 202 274 464 102 90 81 211 83 480 46 251 22 449 3 175 344 233 168 232 47 338 440 37 470 187 471 382 48 433 141 121 224 334 394 218 373 207 252 14 40 444 63 238 342 313 484 374 432 128 294 278 372 109 126 230 467 391 370 70 489 428 393 3...

result:

points 0.71084337350 OK

Test #55:

score: 0
Wrong Answer
time: 0ms
memory: 3716kb

input:

500
188 321
193 4
334 269
259 66
121 396
73 153
332 477
263 67
178 262
185 377
175 53
462 245
390 337
387 200
445 92
387 159
135 263
323 312
143 374
252 47
375 382
303 345
345 283
150 1
66 289
462 82
317 201
169 423
154 193
486 251
368 305
357 375
107 443
437 348
64 55
408 465
315 469
186 328
197 39...

output:

? 3 238 466 2 
? 2 238 466 
? 64 257 494 224 60 246 180 455 388 294 199 170 231 500 369 161 409 400 73 58 491 173 132 256 319 230 303 99 420 179 193 334 352 307 278 85 391 304 469 365 38 452 80 28 118 149 396 242 498 481 163 375 454 67 135 186 78 379 439 171 293 95 30 101 370 
? 5 79 50 249 206 361 ...

result:

wrong output format Unexpected end of file - int32 expected