Submission #835049

#	Time	Username	Problem	Language	Result	Execution time	Memory
835049		_martynas	Game (IOI14_game)	C++11	15 / 100	2 ms	600 KiB

game

#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);
        }
    }
    // cerr << "degs:\n";
    // for(int i = 0; i < n; i++) {
    //     cerr << deg[i] << " ";
    // }
    // cerr << "adj:\n";
    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j < n; j++) {
    //         cerr << adj[i][j];
    //     }
    //     cerr << "\n";
    // }
    return adj[u][v];
}

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