Submission #289259

#	Time	Username	Problem	Language	Result	Execution time	Memory
289259		stoyan_malinin	Game (IOI14_game)	C++14	100 / 100	494 ms	9464 KiB

game

#include "game.h"
//#include "grader.cpp"
 
#include <vector>
#include <cstring>
#include <iostream>
 
using namespace std;
 
const int MAXN = 1505;
 
struct DSU
{
    int parent[MAXN];
    vector <int> nodes[MAXN];
 
    DSU(){}
    DSU(int n)
    {
        for(int i = 0;i<n;i++)
        {
            this->parent[i] = i;
            this->nodes[i] = {i};
        }
    }
 
    int Find(int x)
    {
        if(parent[x]==x) return x;
 
        parent[x] = Find(parent[x]);
        return parent[x];
    }
 
    bool Union(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if(u==v) return false;
        if(nodes[u].size()<nodes[v].size()) swap(u, v);
 
        parent[v] = u;
        for(int x: nodes[v]) nodes[u].push_back(x);
 
        return true;
    }
};
 
DSU T;
bool asked[MAXN][MAXN];
 
void initialize(int n)
{
    T = DSU(n);
    memset(asked, false, sizeof(asked));
}
 
int hasEdge(int u, int v)
{
    if(T.Find(u)==T.Find(v))
    {
        return 1;
    }
 
    asked[u][v] = true;
    asked[v][u] = true;
 
    vector <int> &v1 = T.nodes[T.Find(u)];
    vector <int> &v2 = T.nodes[T.Find(v)];
 
    /*
    cout << "v1:";
    for(int x: v1) cout << " " << x;
    cout << '\n';
 
    cout << "v2:";
    for(int x: v2) cout << " " << x;
    cout << '\n';
    */
 
    bool found = 0;
    for(int x: v1)
    {
        for(int y: v2)
        {
            if(asked[x][y]==false)
            {
                found = 1;
                break;
            }
        }
      
      	if(found==1) break;
    }
 
    if(found==false) T.Union(u, v);
    return found^1;
}

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