Submission #133336

#	Time	Username	Problem	Language	Result	Execution time	Memory
133336		sealnot123	Game (IOI14_game)	C++14	100 / 100	689 ms	22916 KiB

game

#include "game.h"
 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1505;
int n, sq;
int sqg[N][N], g[N][N], l[N], r[N];
int mk[N];
queue<int> bfs;
 
bool check(int a){
    int b = a*sq;
    int i, j = 1;
    for(i = l[b]; i < r[b]; i++){
        mk[i] = 0;
    }
    mk[b] = 1;
    bfs.push(b);
    while(!bfs.empty()){
        int u = bfs.front();
        bfs.pop();
        for(i = l[u]; i < r[u]; i++){
            if(!g[u][i] || mk[i]) continue;
            j++;
            mk[i] = 1;
            bfs.push(i);
        }
    }
    return j == r[b]-l[b];
}
 
bool check_group(){
    int a = (n+sq-1)/sq;
    int i, j = 1;
    for(i = 0; i < a; i++){
        mk[i] = 0;
    }
    mk[0] = 1;
    bfs.push(0);
    while(!bfs.empty()){
        int u = bfs.front();
        bfs.pop();
        for(i = 0; i < a; i++){
            if(!sqg[u][i] || mk[i]) continue;
            mk[i] = 1;
            j++;
            bfs.push(i);
        }
    }
    return j == a;
}
 
void initialize(int nn) {
    n = nn;
    LL i, j, a, b, c;
    sq = sqrt(nn);
    for(i = 0; i < n; i++){
        for(j = i+1; j < n; j++){
            a = i/sq;
            b = j/sq;
            if(a == b) g[i][j] = g[j][i] = 1;
            else sqg[a][b]++,sqg[b][a]++;
        }
        l[i] = i/sq*sq;
        r[i] = min(i/sq*sq+sq, (LL)n);
    }
}
 
int hasEdge(int u, int v) {
    if(u > v) swap(u, v);
    int i, j, a, b, res;
    a = u/sq;
    b = v/sq;
    if(a == b){
        g[u][v] = g[v][u] = 0;
        res = check(a);
        if(!res){
            g[u][v] = g[v][u] = 1;
            return 1;
        }
        return 0;
    }else{
        sqg[a][b]--;
        sqg[b][a]--;
        if(sqg[a][b] != 0) return 0;
        res = check_group();
        if(!res){
            sqg[a][b]++;
            sqg[b][a]++;
            return 1;
        }
        return 0;
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'void initialize(int)':
game.cpp:66:20: warning: unused variable 'c' [-Wunused-variable]
     LL i, j, a, b, c;
                    ^
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:82:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j, a, b, res;
         ^
game.cpp:82:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, a, b, res;
            ^

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