Submission #231893

#	Time	Username	Problem	Language	Result	Execution time	Memory
231893		triple_fault	Game (IOI14_game)	C++14	42 / 100	1092 ms	8728 KiB

game

#include "game.h"
#include <vector>
#include <set>
#include <queue>
#include <cstring>

using namespace std;

#define MAX 1500

vector<vector<int>> adj_list;
set<pair<int, int>> st;

int N;

void initialize(int n) {
    for (int i = 0; i < n; ++i) adj_list.push_back(vector<int>{});

    N = n;
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) st.insert({i, j});
}

int hasEdge(int u, int v) {
    int n = N;
    bool no = true, yes = true;
    vector<vector<int>> adj(adj_list);
    vector<vector<int>> adj2(adj_list);
    if (u > v) swap(u, v);
    st.erase({u, v});
    for (auto &each: st) {
        int x = each.first, y = each.second;
        adj2[x].push_back(y);
        adj2[y].push_back(x);
    }

    queue<int> q; 
    int vis[n]; memset(vis, 0, sizeof vis);
    q.push(u); vis[u] = 1;
    while (!q.empty()) {
        int num = q.front(); q.pop();
        for (auto &each: adj[num]) 
            if (!vis[each]) {
                vis[each] = 1;
                q.push(each);
            }
    }
    int vis2[n]; memset(vis2, 0, sizeof vis2);
    q.push(u); vis2[u] = 1;
    while (!q.empty()) {
        int num = q.front(); q.pop();
        for (auto &each: adj2[num]) {
            if (vis2[each]) continue;
            vis2[each] = 1;
            q.push(each);
        }
    }

    bool pos1 = false, pos2 = true;
    for (int i = 0; i < n; ++i) {
        if (vis[i] == 0) pos1 = true;
        if (vis2[i] == 0) pos2 = false;
    }

    if (pos1 && pos2) return 0;
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
    return 1;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:25:10: warning: unused variable 'no' [-Wunused-variable]
     bool no = true, yes = true;
          ^~
game.cpp:25:21: warning: unused variable 'yes' [-Wunused-variable]
     bool no = true, yes = true;
                     ^~~

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