Submission #285208

#	Time	Username	Problem	Language	Result	Execution time	Memory
285208		stoyan_malinin	Simurgh (IOI17_simurgh)	C++14	30 / 100	3097 ms	6000 KiB

simurgh

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

#include <set>
#include <random>
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 505;
mt19937 rnd(22);

int ASKED = 0;

struct DSU
{
    int parent[MAXN*MAXN];
    int color[MAXN*MAXN];

    DSU(){}
    DSU(int n)
    {
        for(int i = 0;i<=n;i++)
        {
            this->parent[i] = i;
            this->color[i] = -1;
        }
    }

    int Find(int x)
    {
        if(parent[x]==x) return x;

        parent[x] = Find(parent[x]);
        return parent[x];
    }

    bool UnionSimple(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if(u==v) return false;

        parent[v] = u;
        return true;
    }

    bool UnionFull(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if(u==v) return false;

        int newColor = max(color[u], color[v]);
        color[u] = newColor;
        color[v] = newColor;

        parent[v] = u;
        return true;
    }

    int getColor(int x)
    {
        return color[Find(x)];
    }

    void colorize(int x, int col)
    {
        x = Find(x);
        color[x] = col;
    }
};

DSU relationKeeper;

int n;
vector <pair <int, int>> edges;

vector <int> inds;

set <int> constructST()
{
    DSU T(n);
    set <int> ST;

    for(int i: inds)
    {
        if(relationKeeper.getColor(i)==1)
        {
            T.UnionSimple(edges[i].first, edges[i].second);
            ST.insert(i);
        }
    }

    for(int i: inds)
    {
        if(relationKeeper.getColor(i)!=0 && T.UnionSimple(edges[i].first, edges[i].second)==true)
        {
            ST.insert(i);
        }
    }

    return ST;
}

int askVector(vector <int> v)
{
    ASKED++;
    if(ASKED==30*1000) assert(false);

    return count_common_roads(v);
}

int askSet(set <int> s)
{
    ASKED++;
    if(ASKED==30*1000) assert(false);

    vector <int> v;
    for(int x: s) v.push_back(x);

    return count_common_roads(v);
}

vector <int> getReplacements(set <int> ST, int e)
{
    DSU T(n);
    ST.erase(e);

    for(int edgeInd: ST)
        T.UnionSimple(edges[edgeInd].first, edges[edgeInd].second);

    vector <int> out;
    for(int i = 0;i<edges.size();i++)
    {
        if(i==e) continue;
        if(T.Find(edges[i].first)==T.Find(edges[i].second)) continue;

        out.push_back(i);
    }

    return out;
}

int getDiff(set <int> ST, int e1, int e2, int base)
{
    ST.erase(e1);
    ST.insert(e2);

    int res = askSet(ST);
    if(base==res) return 0;
    if(base<res) return 1;
    if(base>res) return 2;
}

void processDif(int e1, int e2, int diff)
{
    if(diff==0)
    {
        relationKeeper.UnionFull(e1, e2);
    }
    else if(diff==1)
    {
        relationKeeper.colorize(e1, 0);
        relationKeeper.colorize(e2, 1);
    }
    else if(diff==2)
    {
        relationKeeper.colorize(e1, 1);
        relationKeeper.colorize(e2, 0);
    }
}

vector <int> set2Vector(set <int> s)
{
    vector <int> out;
    for(int x: s) out.push_back(x);

    return out;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V)
{
    n = N;
    for(int i = 0;i<U.size();i++) edges.push_back({U[i], V[i]});
    relationKeeper = DSU(edges.size());

    for(int i = 0;i<edges.size();i++)
        inds.push_back(i);

    while(true)
    {
        shuffle(inds.begin(), inds.end(), rnd);
        set <int> ST = constructST();

        //cout << "currST: ";
        //for(int x: ST) cout << " " << x;
        //cout << '\n';

        int royalCnt = askSet(ST);
        if(royalCnt==n-1) return set2Vector(ST);

        int e = -1;
        for(int edgeInd: ST)
        {
            if(relationKeeper.getColor(edgeInd)==-1)
            {
                e = edgeInd;
                break;
            }
        }
        //if(e==-1) return {};

        //cout << " --- " << e << " --- " << '\n';

        vector <int> replacements = getReplacements(ST, e);

        //cout << "replacements:";
        //for(int x: replacements) cout << " " << x;
        //cout << '\n';

        for(int edgeInd: replacements)
        {
            if(relationKeeper.getColor(edgeInd)!=-1)
            {
                int diff = getDiff(ST, e, edgeInd, royalCnt);
                processDif(e, edgeInd, diff);

                break;
            }
        }

        if(relationKeeper.getColor(e)==-1)
        {
            for(int edgeInd: replacements)
            {
                //if(edgeInd==e) return {};
                //if(!(edgeInd>=0 && edgeInd<edges.size())) return {};

                int diff = getDiff(ST, e, edgeInd, royalCnt);
                processDif(e, edgeInd, diff);
            }

            if(relationKeeper.getColor(e)==-1)
            {
                relationKeeper.colorize(e, 1);
                for(int edgeInd: replacements)
                    relationKeeper.colorize(edgeInd, 1);
            }
        }

        //cout << "color of " << e << " is " << relationKeeper.getColor(e) << '\n';
    }

    return {};
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> getReplacements(std::set<int>, int)':
simurgh.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int i = 0;i<edges.size();i++)
      |                   ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:188:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(int i = 0;i<U.size();i++) edges.push_back({U[i], V[i]});
      |                   ~^~~~~~~~~
simurgh.cpp:191:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |     for(int i = 0;i<edges.size();i++)
      |                   ~^~~~~~~~~~~~~
simurgh.cpp: In function 'int getDiff(std::set<int>, int, int, int)':
simurgh.cpp:157:1: warning: control reaches end of non-void function [-Wreturn-type]
  157 | }
      | ^

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30