Submission #1146196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146196		zhasyn	Game (IOI14_game)	C++20	15 / 100	1 ms	584 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1500 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;

int n;
bool pred[N][N], has[N][N];
int cnt[N];
void initialize(int g) {
	n = g;
	for(int i = 0; i < n; i++){
		cnt[i] = n - 1;
	}
}
void dfs(int v){
	cnt[v] = 0;
	for(int i = 0; i < n; i++){
		if(pred[i][v] == true || i == v) continue;
		has[i][v] = has[v][i] = true;
		pred[i][v] = pred[v][i] = true;
		cnt[i]--;
		if(cnt[i] == 1) dfs(i);
	}
}
int hasEdge(int u, int v) {
    if(pred[u][v]) return has[u][v];
    
    pred[u][v] = true;
    pred[v][u] = true;
    cnt[v]--;
    cnt[u]--;
    if(cnt[v] == 1) dfs(v);
    if(cnt[u] == 1) dfs(u);
    return 0;
}

// int main() {
  // ios::sync_with_stdio(false);
  // cin.tie(NULL);
  // int kk;
  // cin >> kk;
  // initialize(kk);
  // while(true){
  	// int u, v;
  	// cin >> u >> v;
  	// cout << hasEdge(u, v) << endl;
  // }
  // return 0;
// }

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