Submission #749554

#	Time	Username	Problem	Language	Result	Execution time	Memory
749554		onebit1024	Game (IOI14_game)	C++17	42 / 100	1069 ms	2856 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"

vector<vector<int>>dp,queried;
vector<int>id,sz;

int root(int x){
    if(id[x]==x)return x;
    return id[x] = root(id[x]);
}

void merge(int u, int v){
    u = root(u);
    v = root(v);
    if(u==v)return;
    if(sz[v] > sz[u])swap(v,u);
    for(auto x : dp[v]){
        dp[u].pb(x);
    }
    dp[v].clear();
    id[v] = u;
    sz[u]+=sz[v];
}


void initialize(int n) {
    id.resize(n);
    queried = vector<vector<int>>(n, vector<int>(n));
    sz.resize(n,1);
    dp.resize(n);
    for(int i = 0;i<n;++i)id[i] = i,dp[i].pb(i);
}

int hasEdge(int u, int v) {
    int t = u, r = v;
    u = root(u);
    v = root(v);
    if(u==v)return 1;
    int c = 0;
    for(auto x : dp[u]){
        for(auto y : dp[v]){
            if(!queried[x][y])c++;
        }
    }

    
    queried[t][r] = queried[r][t] = 1;
    if(c==1){
        merge(t,r);
        return 1;
    }
    return 0;
}

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