Submission #421920

#	Time	Username	Problem	Language	Result	Execution time	Memory
421920		Andyvanh1	Game (IOI14_game)	C++14	100 / 100	502 ms	18384 KiB

game

#include <bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
#define vt vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,x) for(int (i) = 0; (i) < (x); (i)++)
#define INF 0x3f3f3f3f
#define MOD 1000000007
 
typedef long long ll;
typedef long double ld;
typedef vt<int> vi;
typedef pair<int,int> pii;
vt<vi> cont;
int p[1503];
int sz[1503];
int many[1503][1503];
set<pii> st;
 
int find(int x){
    return x==p[x] ? x : p[x] = find(p[x]);
}
 
void join(int u, int v){
    u = find(u);
    v = find(v);
    if(u==v)return;
    if(sz[u]>sz[v])swap(u,v);
    sz[v]+=sz[u];
    p[u] = v;
    for(auto& e: cont[u]){
        cont[v].pb(e);
    }
    for(int i = 0; i < v; i++){
        if(i!=u){
            many[i][v]+=many[min(i,u)][max(i,u)];
        }
    }
    for(int i = v+1; i < 1503; i++){
        if(i!=u){
            many[v][i]+=many[min(i,u)][max(i,u)];
        }
    }
}
 
void initialize(int n){
    cont.resize(n);
    for(int i = 0; i < n; i++){
        p[i] = i;
        sz[i] = 1;
        cont[i].pb(i);
        for(int j = i+1; j < n; j++){
            many[i][j] = 1;
        }
    }
 
}
 
int hasEdge(int u, int v){
    int x = find(u);
    int y = find(v);
    if(x>y){
        swap(x,y);
        swap(u,v);
    }
    if(many[x][y]==1){
        join(x,y);
        return 1;
    }else{
        many[x][y]--;
        return 0;
    }
}
 

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