Submission #289390

#	Time	Username	Problem	Language	Result	Execution time	Memory
289390		stoyan_malinin	Game (IOI14_game)	C++14	42 / 100	1096 ms	77500 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 EdgeKeeper
{
    int added[MAXN][MAXN];

    EdgeKeeper()
    {
        memset(this->added, 0, sizeof(this->added));
    }

    void addEdge(int u, int v)
    {
        if(u>v) swap(u, v);
        added[u][v]++;
    }

    void remEdge(int u, int v)
    {
        if(u>v) swap(u, v);
        added[u][v]--;
    }

    int getEdges(int u, int v)
    {
        if(u>v) swap(u, v);
        return added[u][v];
    }
};

vector <pair <int, int>> allEdges;

struct DSU
{
    int parent[MAXN];
    vector <int> nodes[MAXN];
    vector <int> presentEdges[MAXN];

    EdgeKeeper welko;

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

        for(int x: nodes[v]) nodes[u].push_back(x);
        for(int x: presentEdges[v]) presentEdges[u].push_back(x);

        for(int x: presentEdges[v]) welko.remEdge(Find(allEdges[x].first), Find(allEdges[x].second));
        parent[v] = u;
        for(int x: presentEdges[v]) welko.addEdge(Find(allEdges[x].first), Find(allEdges[x].second));

        return true;
    }

    void addEdge(int u, int v, int eInd)
    {
        u = Find(u);
        v = Find(v);

        welko.addEdge(u, v);
        presentEdges[u].push_back(eInd);
        presentEdges[v].push_back(eInd);
    }
};

DSU T;
bool asked[MAXN][MAXN];

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

int eval(int u, int v)
{
    u = T.Find(u);
    v = T.Find(v);
    vector <int> &v1 = T.nodes[u];
    vector <int> &v2 = T.nodes[v];

    //cout << "smart asked: " << T.welko.getEdges(u, v) << '\n';
    /*
    for(int e: T.presentEdges[u])
    {
        if(T.Find(allEdges[e].first)==v || T.Find(allEdges[e].second)==v)
        {
            //cout << allEdges[e].first << " " << allEdges[e].second << '\n';
        }
    }
    */

    return v1.size()*v2.size() - T.welko.getEdges(u, v);
}

int evalSlow(int u, int v)
{
    vector <int> &v1 = T.nodes[T.Find(u)];
    vector <int> &v2 = T.nodes[T.Find(v)];

    int found = 0;
    for(int x: v1)
    {
        for(int y: v2)
        {
            if(asked[x][y]==false)
            {
                found++;
            }
            else
            {
                cout << "asked: " << x << " " << y << '\n';
            }
        }
    }

    return found;
}

int hasEdge(int u, int v)
{
    T.addEdge(u, v, allEdges.size());
    allEdges.push_back({u, v});

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

    asked[u][v] = true;
    asked[v][u] = true;

    int found = eval(u, v);
    //assert(eval(u, v)==evalSlow(u, v));
    //cout << eval(u, v) << " == " << evalSlow(u, v) << '\n';

    //evalSlow(u, v);

    if(found==0)
    {


        //cout << "u: " << '\n';
        //for(int x: T.presentEdges[T.Find(u)]) cout << allEdges[x].first << " " << allEdges[x].second << '\n';

        //cout << "v: " << '\n';
        //for(int x: T.presentEdges[T.Find(v)]) cout << allEdges[x].first << " " << allEdges[x].second << '\n';


        T.Union(u, v);

        //cout << " -> " << T.welko.getEdges(T.Find(4), T.Find(0)) << '\n';
        return 1;
    }
    else
    {
        //cout << " -> " << T.welko.getEdges(T.Find(4), T.Find(0)) << '\n';
        return 0;
    }

}
/*
4
0 2
1 3
0 3
1 2
0 1
2 3

7
2 4
4 6
0 6
1 3
0 1
1 5
0 2
3 5
2 3
3 4
2 6
1 6
1 2
0 5
5 6
0 3
3 6
4 5
---------
2 5
0 4
1 4
*/

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