Submission #879660

#	Time	Username	Problem	Language	Result	Execution time	Memory
879660		Rifal	Game (IOI14_game)	C++14	100 / 100	290 ms	26604 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1500 + 5;
int cnt[N][N];
int p[N], ran[N];
int nn;
int fin(int x) {
    if(p[x] == x) return x;
    else return p[x] = fin(p[x]);
}
void uni(int x, int y) {
    if(ran[x] < ran[y]) swap(x,y);
    if(ran[x] == ran[y]) ran[x]++;
    p[y] = x;
}
void initialize(int n) {
    nn = n; 
    for(int i = 0; i < n; i++) {
        p[i] = i; 
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            cnt[i][j] = 1;
        }
    }
}
int hasEdge(int u, int v) {
    int uu = fin(u), vv = fin(v);
  //  cout << uu << ' ' << vv << 'k' << endl;
  //  cout << cnt[uu][vv] << ' ' << cnt[vv][uu] << 'a' << endl;
    cnt[uu][vv]--;
    cnt[vv][uu]--;
  //  cout << cnt[uu][vv] << ' ' << cnt[vv][uu] << 'b' << endl;
    if(cnt[uu][vv] == 0) {
        uni(uu,vv);
        int nw = fin(uu);
        bool ok[nn] = {};
        for(int i = 0; i < nn; i++) {
            if(ok[fin(i)] == 0 && nw != fin(i)) {
               // cout << uu << ' ' << vv << ' ' << fin(i) << endl;
               // cout << cnt[uu][fin(i)] << ' ' << cnt[vv][fin(i)] << 'h' << endl;
                cnt[nw][fin(i)] = cnt[uu][fin(i)] + cnt[vv][fin(i)];
                cnt[fin(i)][nw] = cnt[nw][fin(i)];
               // cout << cnt[fin(i)][nw] << ' ' <<  cnt[nw][fin(i)] << 'z' << endl;
                ok[fin(i)] = 1;
            }
        }
        return 1;
    }
    else {
        return 0;
    }
}

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