Submission #113597

#	Time	Username	Problem	Language	Result	Execution time	Memory
113597		MladenP	Game (IOI14_game)	C++17	100 / 100	480 ms	24848 KiB

game

//#include "grader.h"
#include <bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF LLONG_MAX
#define INF INT_MAX
#define EPS 1e-9
#define MAXN 1510
using namespace std;

struct uNode {
    int parent, cnt;
};
uNode dsu[MAXN];
int edges[MAXN][MAXN];
int Root(int x) {
    while(x != dsu[x].parent) {
        dsu[x].parent = dsu[dsu[dsu[x].parent].parent].parent;
        x = dsu[x].parent;
    }
    return x;
}
int N;
void Connect(int a, int b) {
    int rootA = Root(a), rootB = Root(b);
    if(dsu[rootA].cnt > dsu[rootB].cnt) {
        dsu[rootB].parent = rootA;
        dsu[rootA].cnt += dsu[rootB].cnt;
        for(int i = 1; i <= N; i++) {
            edges[min(i, rootA)][max(i, rootA)] += edges[min(i, rootB)][max(i, rootB)];
        }
    }
    else  {
        dsu[rootA].parent = rootB;
        dsu[rootB].cnt += dsu[rootA].cnt;
        for(int i = 0; i < N; i++) {
            edges[min(i, rootB)][max(i, rootB)] += edges[min(i, rootA)][max(i, rootA)];
        }
    }
}
void initialize(int n) {
    N = n;
    for(int i = 0; i < n; i++) {
        dsu[i].parent = i; dsu[i].cnt = 1;
    }
}

int hasEdge(int u, int v) {
    int rootV = Root(v), rootU = Root(u);
    int minn = min(rootV, rootU); rootU = max(rootU, rootV), rootV = minn;
    int totEdges = dsu[rootV].cnt*dsu[rootU].cnt-edges[rootV][rootU];
    ///PRINT(totEdges);
    ///PRINT(dsu[rootV].cnt);
    ///PRINT(totEdges);
    if(totEdges == 1) return Connect(rootV, rootU), 1;
    else return edges[rootV][rootU]++, 0;
}
/*
int main() {
    int n; scanf("%d", &n);
    initialize(n);
    for(int i = 0; i < (n-1)*n/2; i++) {
        int x, y; scanf("%d%d", &x, &y);
        printf("%d\n", hasEdge(x, y));
    }
}
*/

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