Submission #835049

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
835049	2023-08-23 07:02:53	_martynas	Game (IOI14_game)	C++11	15 / 100	2 ms	600 KiB

game

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 "game.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1505;
int n;
int deg[mxn];
bool resp[mxn][mxn];
bool adj[mxn][mxn];
void initialize(int N) {
    n = N;
    for(int i = 0; i < n; i++) deg[i] = n-1;
}
int hasEdge(int u, int v) {
    if(adj[u][v]) return true;
    queue<int> q;
    deg[u]--; if(deg[u] == 1) q.push(u);
    deg[v]--; if(deg[v] == 1) q.push(v);
    resp[u][v] = resp[v][u] = true;
    while(!q.empty()) {
        int i = q.front(); q.pop();
        for(int j = 0; j < n; j++) if(i != j && !resp[i][j] && !adj[i][j]) {
            adj[i][j] = adj[j][i] = true;
            deg[j]--; if(deg[j] == 1) q.push(j);
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58