Submission #289334

#	Time	Username	Problem	Language	Result	Execution time	Memory
289334		stoyan_malinin	Game (IOI14_game)	C++14	42 / 100	1059 ms	26336 KiB

game

#include "game.h"
//#include "grader.cpp"

#include <map>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>

using namespace std;

const int MAXN = 1505;

struct Profile
{
    int root1, root2;
    int sz1 = 0, sz2 = 0;

    Profile(){}
    Profile(int root1, int root2, int sz1, int sz2)
    {
        this->root1 = root1;
        this->root2 = root2;
        //this->sz1 = sz1;
        //this->sz2 = sz2;
    }
};

bool operator <(Profile A, Profile B)
{
    if(A.root1!=B.root1) return A.root1<B.root1;
    if(A.root2!=B.root2) return A.root2<B.root2;
    if(A.sz1!=B.sz1) return A.sz1<B.sz1;
    return A.sz2<B.sz2;
}

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;
    }
};

Profile makeProfile(int u, int v, DSU &T)
{
    u = T.Find(u);
    v = T.Find(v);

    Profile out;
    out.root1 = u;
    out.root2 = v;
    out.sz1 = T.nodes[u].size();
    out.sz2 = T.nodes[v].size();
    if(out.sz1<out.sz2)
    {
        swap(out.root1, out.root2);
        swap(out.sz1, out.sz2);
    }

    return out;
}

DSU T;
bool asked[MAXN][MAXN];
map <Profile, int> memo;

void initialize(int n)
{
    T = DSU(n);
    memset(asked, false, sizeof(asked));
}

int evalProfile(Profile p, int &lastInd)
{
    int u = p.root1, v = p.root2;
    vector <int> &v1 = T.nodes[T.Find(u)];
    vector <int> &v2 = T.nodes[T.Find(v)];

    for(int i = lastInd;i<v1.size();i++)
    {
        for(int j = 0;j<v2.size();j++)
        {
            if(asked[ v1[i] ][ v2[j] ]==false)
            {
                lastInd = i;
                return 1;
            }
        }
    }

    return 0;
}

int hasEdge(int u, int v)
{
    if(T.Find(u)==T.Find(v))
    {
        return 1;
    }
    if(asked[u][v]==true) return 0;

    Profile p = makeProfile(u, v, T);
    if(memo.find(p)==memo.end()) memo[p] = 0;

    //cout << "Profile: " << p.root1 << " " << p.root2 << " " << p.sz1 << " " << p.sz2 << '\n';
    //cout << memo[p] << " == " << evalProfile(p) << '\n';
    //assert(memo[p]==evalProfile(p));

    asked[u][v] = true;
    asked[v][u] = true;
    int found = evalProfile(p, memo[p]);

    //cout << memo[p] << '\n';

    if(found==0)
    {
        T.Union(u, v);
        memo.erase(p);

        return 1;
    }
    else
    {
        return 0;
    }
}
/*
4
0 2
1 3
0 3
1 2
0 1
2 3
*/

Compilation message (stderr)

game.cpp: In function 'int evalProfile(Profile, int&)':
game.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = lastInd;i<v1.size();i++)
      |                         ~^~~~~~~~~~
game.cpp:111:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0;j<v2.size();j++)
      |                       ~^~~~~~~~~~

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