Submission #855606

#	Time	Username	Problem	Language	Result	Execution time	Memory
855606		_uros9	Game (IOI14_game)	C++17	100 / 100	411 ms	34128 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;

vector<int> par(2000),rnk(2000);
vector<vector<int>> povezanost(2000,vector<int>(2000));
int n;
void initialize(int nn){
    n=nn;
    for(int i=0; i<n; i++){
        par[i]=i;
        rnk[i]=0;
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            povezanost[i][j]=1;
    }
}
int ulp(int node){
    if(par[node]==node)
        return node;
    return par[node]=ulp(par[node]);
}
void spajaj(int a,int b){
    a=ulp(a);b=ulp(b);
    if(a==b) return;
    if(rnk[b]>rnk[a])
        swap(a,b);
    par[b]=a;
    if(rnk[b]==rnk[a])
        rnk[a]++;
}
int hasEdge(int u,int v){
    if(ulp(u)==ulp(v)) return 0;
    u=ulp(u);v=ulp(v);
    if(rnk[v]>rnk[u])
        swap(v,u);
    if(povezanost[u][v]!=1&&povezanost[v][u]!=1){
        povezanost[u][v]--;
        povezanost[v][u]--;
        return 0;
    }
    for(int i=0; i<n; i++){
        //if(i==v||ulp(i)==ulp(u)) continue;
        povezanost[u][i]+=povezanost[v][i];
        povezanost[i][u]=povezanost[u][i];
    }
    spajaj(u,v);
    return 1;
}

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