Submission #959682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959682	2024-04-08T18:34:00 Z	vjudge1	Game (IOI14_game)	C++17	15 / 100	3 ms	504 KB

game

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1500;
 
int n, sum, deg[N], cnt[N];
unordered_set<int> vis, adj[N];
 
void dfs(int x, int k) {
    vis.insert(x);
 
    sum++;
    if (sum > k) return;
 
    for (int y : adj[x]) {
        if (vis.find(y) != vis.end()) continue;
 
        dfs(y, k);
        if (sum > k) return;
    }
}
 
void initialize(int NN) {
    n = NN;
 
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) {
        deg[i] = n;
        cnt[n]++;
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            adj[i].insert(j);
            adj[j].insert(i);
        }
    }
}
 
int hasEdge(int u, int v) {
    adj[u].erase(v);
    adj[v].erase(u);
 
    deg[u]--;
    deg[v]--;

    cnt[deg[u]]++;
    cnt[deg[v]]++;

    if (cnt[deg[u]] >= deg[u]) {
        vis.clear();
        sum = 0;
        dfs(u, deg[u]);
        if (sum <= deg[u]) {
            cnt[deg[u]]--;
            cnt[deg[v]]--;

            deg[u]++;
            deg[v]++;

            adj[u].insert(v);
            adj[v].insert(u);

            return 1;
        }
    }
 
    if (cnt[deg[v]] >= deg[v]) {
        vis.clear();
        sum = 0;
        dfs(v, deg[v]);
        if (sum <= deg[v]) {
            cnt[deg[u]]--;
            cnt[deg[v]]--;

            deg[u]++;
            deg[v]++;

            adj[u].insert(v);
            adj[v].insert(u);

            return 1;
        }
    }
 
    return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	1 ms	504 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct

Subtask #2

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	432 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	3 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Incorrect	1 ms	348 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3

0 / 58.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Incorrect	2 ms	348 KB	Output isn't correct
26	Halted	0 ms	0 KB	-