Submission #584553

#	Time	Username	Problem	Language	Result	Execution time	Memory
584553		ponkung	Game (APIO22_game)	C++17	60 / 100	4042 ms	17820 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int mx[300005],n,m,mn[300005],u,val,type;
vector<int> g[300005],rev[300005];
queue<int> q;
void init(int N, int M) {
    n=N;
    m=M;
    for(int i=1;i<=n;i++)
    {
        mx[i]=-1e9;
        mn[i]=1e9;
    }
    for(int i=1;i<=m;i++)mx[i]=i,mn[i]=i;
}

int add_teleporter(int x, int y) {
      x+=1;
      y+=1;
      g[x].pb(y);
      rev[y].pb(x);
      if(x>=y&&x>=1&&x<=m&&y>=1&&y<=m)return 1;
      mn[x]=min(mn[x],mn[y]);
      val=mn[y];
      q.push(x);
      while(!q.empty())
      {
          u=q.front();
          q.pop();
          for(auto node:rev[u])
          {
              if(val<mn[node])
              {
                  mn[node]=val;
                  q.push(val);
              }
          }
      }
      mx[y]=max(mx[y],mx[x]);
      val=mx[x];
      q.push(y);
      while(!q.empty())
      {
          u=q.front();
          q.pop();
          for(auto node:g[u])
          {
              if(val>mx[node])
              {
                  mx[node]=val;
                  q.push(node);
              }
          }
      }
      type=0;
      for(int i=m+1;i<=n;i++)
      {
          if(mx[i]>=mn[i])
          {
              type=1;
          }
      }
      return type;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 40