Submission #986463

#	Time	Username	Problem	Language	Result	Execution time	Memory
986463		Yazan_SA	Game (IOI14_game)	C++14	42 / 100	1085 ms	5720 KiB

game

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

int N=1e9;
map<pair<int,int>,int>mp2;
vector<vector<int>>gr;
bool able(int x, int v, vector<bool>&vis)
{
    if(x==v)return 1;
    vis[x]=1;
    for(auto c:gr[x])
    {
        if(vis[c])continue;
        if(able(c,v,vis))return 1;
    }
    return 0;
}
bool able2(int u, int v)
{
    for(int i=0; i<(int)gr[u].size(); i++)
    {
        if(gr[u][i]==v)gr[u].erase(gr[u].begin()+i);
    }
    for(int i=0; i<(int)gr[v].size(); i++)
    {
        if(gr[v][i]==u)gr[v].erase(gr[v].begin()+i);
    }
    vector<bool>vis((int)gr.size());
    bool o=able(u,v,vis);
    gr[v].push_back(u);
    gr[u].push_back(v);
    return o;
}
void initialize(int n)
{
    gr.resize(n);
    for(int i=0; i<n; i++)
    {
        for(int j=0;j<n; j++)
        {
            if(i==j)continue;
            gr[i].push_back(j);
        }
    }
    return;
}
int hasEdge(int u, int v)
{
    if(mp2[{u,v}])return mp2[{u,v}]%2;
    if((int)gr[u].size()==1 || (int)gr[v].size()==1 || !able2(u,v))
    {
        mp2[{u,v}]=1;
        mp2[{v,u}]=1;
        return 1;
    }
    mp2[{u,v}]=2;
    mp2[{v,u}]=2;
    for(int i=0; i<(int)gr[u].size(); i++)
    {
        if(gr[u][i]==v)gr[u].erase(gr[u].begin()+i);
    }
    for(int i=0; i<(int)gr[v].size(); i++)
    {
        if(gr[v][i]==u)gr[v].erase(gr[v].begin()+i);
    }
    // cout<<"1"<<endl;
    return 0;
}

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