Submission #580630

#	Time	Username	Problem	Language	Result	Execution time	Memory
580630		MrDeboo	Game (IOI14_game)	C++17	42 / 100	1086 ms	3316 KiB

game

#include "game.h"
#include"bits/stdc++.h"
using namespace std;
int n;
bool bl[1500][1500];
bool use[1500][1500];
vector<pair<int,int>>vctpr;
bool SUIII(){
    vector<pair<int,int>>vctpor;
    int cnt=1;
    vector<bool>vis(n);
    deque<int>dq={rand()%n};
    vis[dq.back()]=1;
    while(dq.size()){
        int a=dq.front();
        dq.pop_front();
        vector<int>g;
        for(int i=0;i<n;i++){
            if(!vis[i]&&bl[a][i])g.push_back(i);
        }
        vector<int>G;
        while(g.size()){
            swap(g[rand()%g.size()],g.back());
            G.push_back(g.back());
            g.pop_back();
        }
        for(auto &i:G){
            vis[i]=1;
            vctpor.push_back({a,i});
            vctpor.push_back({i,a});
            cnt++;
            dq.push_back(i);
        }
    }
    if(cnt!=n)return 0;
    for(auto &i:vctpr)use[i.first][i.second]=0;
    vctpr=vctpor;
    for(auto &i:vctpr)use[i.first][i.second]=1;
    return 1;
}

void initialize(int N){
    n=N;
    memset(bl,1,sizeof bl);
    srand(time(NULL));
    SUIII();
}

int hasEdge(int u, int v){
    bl[u][v]=0;
    bl[v][u]=0;
    if(SUIII())return 0;
    bl[u][v]=1;
    bl[v][u]=1;
    return 1;
}

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