Submission #667514

#	Time	Username	Problem	Language	Result	Execution time	Memory
667514		Bogdan1110	Game (IOI14_game)	C++14	100 / 100	397 ms	28240 KiB

game

#include <bits/stdc++.h>
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element

const double eps = 0.00000001;
const int NMAX = 2010;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;
int N;
int par[NMAX];
int sz[NMAX];
int kol[NMAX][NMAX];

int rod(int n) {
    while(n!=par[n]) n = par[n];
    return n;
}

void povezi(int a, int b) {
    if (sz[a] < sz[b]) swap(a,b);
    for (int i = 0; i < N ; i++) {
        kol[a][i] += kol[b][i];
        kol[i][a] += kol[b][i];
    }
    sz[a] += sz[b];
    par[b] = a;
}

int hasEdge(int u, int v) {
    u = rod(u);
    v = rod(v);
    if ( u == v) return 1;
    if ( kol[u][v] == sz[u] * sz[v] -1 ) {
        povezi(u,v);
        return 1;
    }
    kol[u][v]++;
    kol[v][u]++;
    return 0;
}

void initialize(int n) {
    N = n;
    for (int i = 0 ; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
}

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