제출 #595093

#제출 시각아이디문제언어결과실행 시간메모리
595093shrimb게임 (IOI14_game)C++17
100 / 100
997 ms17084 KiB
#include"bits/stdc++.h" using namespace std; #include "game.h" bitset<1500> adj[1500], st[1500], badst; int n; // adj[i][j] = 1 if there is an edge from i to j which still exists // st[i][j] = 1 if the edge from i to j is an edge in the st // badst[i] = 1 if the node i is connected to v through the edges of the st after edge u v is deleted vector<int> madj[1500]; void initialize(int N) { n = N; for (int i = 0 ; i < n ; i++) { if (i + 1 < n) { st[i][i + 1] = 1; st[i + 1][i] = 1; madj[i].push_back(i + 1); madj[i + 1].push_back(i); } adj[i] = 0; for (int j = 0 ; j < n ; j++) { adj[i][j] = i != j; } } } int badu; void dfs (int cur) { // cerr << cur << endl; badst[cur] = 1; for (int j : madj[cur]) { if (j != badu and badst[j] == 0) dfs(j); } } int hasEdge(int u, int v) { if (!st[u][v]) { adj[u][v] = 0; adj[v][u] = 0; return 0; } badst = 0; badu = u; dfs(v); adj[u][v] = adj[v][u] = 0; for (int i = 0 ; i < n ; i++) { if (!badst[i]) { auto j = adj[i] & badst; int k = j._Find_first(); if (k < n) { st[u][v] = st[v][u] = 0; st[i][k] = st[k][i] = 1; madj[u].erase(find(madj[u].begin(), madj[u].end(), v)); madj[v].erase(find(madj[v].begin(), madj[v].end(), u)); madj[i].push_back(k); madj[k].push_back(i); // cerr << i << " " << k << endl; return 0; } } } adj[u][v] = adj[v][u] = 1; return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...