Submission #290910

#	Time	Username	Problem	Language	Result	Execution time	Memory
290910		davi_bart	Game (IOI14_game)	C++17	100 / 100	824 ms	16248 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ld long double
bool p[1600][1600];
unordered_map<int,int> arc[170];
int rad,N;
int hasEdge(int u, int v) {
    int ga=u/rad,gb=v/rad;
    if(ga==gb){
      p[u][v]=0;
      p[v][u]=0;
      vector<bool> vis(rad+2,0);
      queue<int> q;
      q.push(u);

      while(!q.empty()){
        int pos=q.front();
        q.pop();
        if(pos/rad!=ga)continue;
        if(vis[pos%rad])continue;
        vis[pos%rad]=1;

        for(int i=rad*ga;i<rad*(ga+1);i++){
          if(i>=N)break;
          if(p[pos][i])q.push(i);
        }
        /*auto y=p[pos].lower_bound(rad*ga);
        if(y==p[pos].end())continue;
        while((*y)>=rad*ga && (*y)<rad*(ga+1)){
          q.push(*y);
          y++;
          if(y==p[pos].end())break;
        }*/
      }
      bool ok=1;
      for(int i=0;i<rad;i++){
        if(ga*rad+i>=N)break;
        if(vis[i]==0){
          ok=0;
          break;
        }
      }
      if(ok==0){
        p[u][v]=1;
        p[v][u]=1;
        return 1;
      }
      return 0;
    }
    p[u][v]=0;
    p[v][u]=0;
    arc[ga][gb]--;
    arc[gb][ga]--;
    bool ok=0;
    if(arc[ga][gb]>0)ok=1;
    else{
      arc[ga].erase(gb);
      arc[gb].erase(ga);
    }
    vector<bool> vis(N/rad+2,0);
    queue<int> q;
    q.push(ga);
    while(!q.empty() && ok==0){
      int pos=q.front();
      q.pop();
      if(pos==gb){
        ok=1;
        break;
      }
      if(vis[pos])continue;
      vis[pos]=1;
      for(auto &[k,_]:arc[pos]){
        if(k==gb){
          ok=1;
          break;
        }
        if(vis[k]==0)q.push(k);
      }
    }
    if(ok==0){
      p[u][v]=1;
      p[v][u]=1;
      arc[ga][gb]=1;
      arc[gb][ga]=1;
      return 1;
    }
    return 0;
}
void initialize(int n){
  rad=min(15,n);
  N=n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      p[i][j]=1;
      arc[i/rad][j/rad]++;
    }
  }
}

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