Codeforces Round #746 (Div. 2)

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

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

const int M = 1e5 + 7;
ll num[M];

int main() {
    int t = read();
    while(t --) {
        ll n = read(), h = read();
        for(int i = 0; i < n; i ++) {
            num[i] = read();
        }
        sort(num, num + n);
        ll a = num[n - 1], b = num[n - 2];
        ll ans = h / (a + b);
        ans *= 2;
        if(h % (a + b) > 0 && h % (a + b) > a) ans += 2;
        else if (h % (a + b) > 0 && h % (a + b) <= a) ans += 1;
        cout << ans <

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
const int M = 1e5 + 7;
int num[M], tmp[M];

int main() {
    int t = read();
    while(t --) {
        ll n = read(), x = read();
        for(int i = 0; i < n; i ++) {
            num[i] = read();
            tmp[i] = num[i];
        }

        sort(tmp, tmp + n);

        bool flag = true;
        for(int i = 0 ; i < n; i ++) {
            if(i < x && n - i - 1 < x && tmp[i] != num[i]) flag = false;
        }
        if(flag)
            cout << "YES" << endl;
        else 
            cout << "NO" << endl;
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

const int M = 1e5 + 7;

struct Node {
    int to, nxt;
} tr[M * 2];

int head[M], idx, num[M], xxor[M], all, cnt;

void add(int u, int v) {
    tr[idx] = {v, head[u]};
    head[u] = idx ++;
}

int dfs(int u, int fa) {
    int now = num[u];
    for(int i = head[u]; ~i; i = tr[i].nxt) {
        int j = tr[i].to;
        if(j != fa) {
            now ^= dfs(j, u);
        }
    }
    if(now == all) {
        cnt ++;
        return 0;
    }
    return xxor[u] = now;
}

int main() {
    int t = read();
    while(t --) {
        idx = 0, all = 0, cnt = 0;
        ll n = read(), k = read();
        for(int i = 1; i <= n; i ++) {
            num[i] = read();
            head[i] = -1;
            all ^= num[i];
        }

        for(int i = 1; i < n ; i ++) {
            int u = read(), v = read();
            add(u, v);
            add(v, u);
        }
        dfs(1, - 1);
        if(all == 0) {
            cout << "YES" << endl;
        } else {
            dfs(1, -1);
            if(k >= 3 && cnt > 2) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0', ch = getchar();}
    return x * f;
}
const int M = 1e3 + 7;
typedef pair<int, int> PII;
vector<int> tr[M];
vector<PII> edge;
int in[M], out[M], cnt = 1;

void dfs(int now, int fa) {
    edge.push_back({now, fa});
    for(int i = 0; i < (int)tr[now].size(); i ++) {
        if(fa != tr[now][i]) {
            dfs(tr[now][i], now);
        }
    }
}

void query(int n, int ans) {
    int l = 1, r = n - 1; // 第一个点不会是答案
    while(true) {
        if(l == r) {
            printf("! %d %d\n", edge[l].first, edge[l].second);
            break;
        }
        int mid = l + r >> 1;
        set<int> st;
        for(int i = l; i <= mid; i ++) st.insert(edge[i].first), st.insert(edge[i].second);
        cout << "? " << st.size();
        for(auto i : st) cout << " " << i ;
        cout << endl;
        int now = read();
        if(now == ans) r = mid;
        else  l = mid + 1;
    } 
}

int main() {
    int n = read();
    for(int i = 1; i < n ; i ++) {
        int u = read(), v = read();
        tr[u].push_back(v);
        tr[v].push_back(u);
    }

    dfs(1, 1);
    cout << "? " << n;
    for(int i = 1; i <= n; i ++) cout << " " << i;
    cout << endl;
    int ans = read();

    query(n, ans);
    return 0;
}