QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690836#4926. Where Is the Root?Mher7770 3ms3924kbC++205.9kb2024-10-31 05:18:382024-10-31 05:18:40

Judging History

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

  • [2024-10-31 05:18:40]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:3924kb
  • [2024-10-31 05:18:38]
  • 提交

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 && (int)g[i].size() >= 3) {
            mn = sz;
            u = i;
        }
    }
    while (1) {
        vi v;
        used[u] = 1;
        int gag = 0;
        for (auto to : g[u]) {
            if (used[to]) {
                gag = 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 (gag) {
                if (qry({ v[l],gag })) {
                    u = v[l];
                }
                else {
                    u = v[r];
                }
            }
            else {
                if (qry({ 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;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 7
Accepted
time: 1ms
memory: 3692kb

input:

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

output:

? 3 6 2 1 
? 2 6 2 
? 2 6 1 
! 2

result:

ok OK

Test #3:

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

input:

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

output:

? 4 2 1 9 7 
? 2 2 1 
? 2 2 7 
? 1 6 
? 2 8 3 
? 2 8 1 
! 8

result:

ok OK

Test #4:

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

input:

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

output:

? 3 4 3 1 
? 2 4 3 
? 2 4 1 
? 1 6 
! 6

result:

ok OK

Test #5:

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

input:

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

output:

? 4 8 5 3 1 
? 2 8 5 
? 2 3 8 
! 3

result:

ok OK

Test #6:

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

input:

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

output:

? 5 8 3 7 1 6 
! 9

result:

ok OK

Test #7:

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

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 10
Accepted
time: 0ms
memory: 3916kb

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 
? 2 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: 1ms
memory: 3924kb

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 
? 2 14 1 
! 14

result:

ok OK

Test #26:

score: 10
Accepted
time: 0ms
memory: 3684kb

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

output:

? 4 19 23 9 2 
? 2 19 23 
? 2 9 19 
? 2 26 1 
? 2 26 7 
? 1 18 
? 2 22 5 
? 2 22 1 
? 3 8 29 16 
! 5

result:

ok OK

Test #27:

score: 10
Accepted
time: 1ms
memory: 3696kb

input:

30
11 30
5 27
13 8
29 2
17 23
1 15
21 16
3 1
9 20
26 8
9 12
12 29
17 22
1 2
12 16
5 10
19 18
1 14
5 7
18 12
8 1
5 25
29 24
3 28
5 8
12 23
6 4
1 6
11 23
YES
NO
YES
NO
YES
YES
NO

output:

? 6 15 3 2 14 8 6 
? 3 15 3 2 
? 5 15 3 2 14 8 
? 2 14 15 
? 3 13 26 5 
? 2 13 26 
? 2 13 1 
! 26

result:

ok OK

Test #28:

score: 10
Accepted
time: 1ms
memory: 3632kb

input:

30
28 6
22 15
7 26
24 17
16 18
30 19
25 5
16 11
11 13
6 1
24 6
27 24
29 14
17 21
5 20
23 2
12 27
20 29
9 23
15 4
24 29
16 6
10 26
5 30
23 27
9 15
1 7
3 1
8 11
YES
YES
NO
YES
YES
NO
NO

output:

? 4 17 6 27 29 
? 2 17 6 
? 2 17 29 
? 3 28 1 16 
? 2 28 1 
? 2 28 24 
? 2 7 3 
! 1

result:

ok OK

Test #29:

score: 10
Accepted
time: 1ms
memory: 3696kb

input:

30
25 21
29 13
16 30
22 27
29 9
6 19
11 20
17 2
5 24
20 7
28 26
17 30
12 23
12 19
12 5
1 27
20 5
29 19
21 23
11 4
26 10
15 5
1 14
28 23
1 11
30 18
1 30
8 21
12 3
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES

output:

? 4 24 12 20 15 
? 2 24 12 
? 2 20 24 
? 2 11 7 
? 2 11 5 
? 2 4 1 
? 2 4 20 
? 3 27 14 30 
? 2 27 14 
? 3 16 17 18 
? 2 16 17 
? 2 16 1 
? 1 2 
! 2

result:

ok OK

Test #30:

score: 10
Accepted
time: 0ms
memory: 3628kb

input:

30
11 29
30 15
11 30
23 12
1 21
30 1
18 1
7 23
1 28
6 9
9 24
8 7
30 8
9 26
30 27
16 6
30 5
20 29
14 25
14 28
24 11
26 19
4 22
10 22
3 28
2 7
28 22
1 17
11 13
YES
YES
YES
NO
YES
NO

output:

? 6 15 11 1 8 27 5 
? 3 15 11 1 
? 2 15 11 
? 2 15 5 
? 3 29 24 13 
? 2 29 24 
! 13

result:

ok OK

Test #31:

score: 10
Accepted
time: 0ms
memory: 3860kb

input:

30
11 27
27 26
23 13
8 30
14 9
1 5
22 16
1 14
1 10
17 21
26 25
9 28
3 13
14 3
12 30
1 15
26 19
26 1
29 2
7 14
17 4
2 9
20 9
1 30
14 17
20 18
6 14
24 19
8 22
YES
NO
YES
NO
YES
NO
YES

output:

? 6 5 14 10 15 26 30 
? 3 5 14 10 
? 5 5 14 10 15 26 
? 2 15 5 
? 3 27 25 19 
? 2 27 25 
? 1 24 
! 24

result:

ok OK

Test #32:

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

input:

30
8 23
5 11
11 15
26 27
28 5
17 22
17 16
21 20
12 4
12 10
7 3
24 29
30 10
3 12
30 6
21 22
23 1
6 25
9 19
14 2
20 18
2 29
7 9
13 24
15 18
27 16
8 28
19 13
14 26
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

output:

? 3 4 10 3 
? 2 4 10 
? 1 7 
? 1 9 
? 1 19 
? 1 13 
? 1 24 
? 1 29 
? 1 2 
? 1 14 
? 1 26 
? 1 27 
? 1 16 
? 1 17 
? 1 22 
? 1 21 
? 1 20 
? 1 18 
? 1 15 
? 1 11 
? 1 5 
? 1 28 
? 1 8 
? 1 23 
? 1 1 
! 1

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 
? 2 89 156 
? 8 21 363 263 475 295 45 171 84 
? 4 21 363 263 475 
? 6 21 363 263 475 295 45 
? 2 295 139 
? 3 147 124 431 
? 2 147 124 
? 2 147 89 
? 6 271 206 368 188 195 5 
? 3 271 206 368 
? 2 271 206 
? 4 4...

result:

wrong output format Unexpected end of file - int32 expected