Submission #726611

#	Time	Username	Problem	Language	Result	Execution time	Memory
726611		abcvuitunggio	Game (APIO22_game)	C++17	12 / 100	19 ms	30832 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=707;
vector <int> ke[300001][4],ve;
int dp[300001][2],a[300001][2],n,k,cnt;
void init(int N, int K) {
    n=N;
    k=K;
    for (int i=0;i<n;i++){
        a[i][0]=(i<k?i:n+1);
        a[i][1]=(i<k?i:-2);
    }
    memset(dp,-1,sizeof(dp));
}
int f(int u, int i){
    if (dp[u][i]!=-1)
        return dp[u][i];
    ve.push_back(u);
    dp[u][i]=a[u][i];
    for (int v:ke[u][i+2])
        dp[u][i]=(i?max(dp[u][i],f(v,i)):min(dp[u][i],f(v,i)));
    return dp[u][i];
}
void dfs(int u, int i, int s){
    if (a[u][i]!=-2&&a[u][i]!=n+1)
        return;
    a[u][i]=s;
    for (int v:ke[u][i^1])
        dfs(v,i,s);
}
void reset(){
    for (int i=0;i<n;i++){
        ke[i][0].insert(ke[i][0].end(),ke[i][2].begin(),ke[i][2].end());
        ke[i][2].clear();
        ke[i][1].insert(ke[i][1].end(),ke[i][3].begin(),ke[i][3].end());
        ke[i][3].clear();
    }
    for (int i=0;i<n;i++){
        a[i][0]=n+1;
        a[i][1]=-2;
    }
    for (int i=0;i<k;i++)
        dfs(i,0,i);
    for (int i=k-1;i>=0;i--)
        dfs(i,1,i);
}
int add_teleporter(int u, int v) {
    cnt++;
    if (cnt%sz==0)
        reset();
    for (int i:ve)
        dp[i][0]=dp[i][1]=-1;
    ve.clear();
    ke[u][2].push_back(v);
    ke[v][3].push_back(u);
    int a=f(u,1),b=f(v,0);
    if (a<0||a>=n||b<0||b>=n)
        return 0;
    return (a>=b);
}

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