Submission #700854

#	Time	Username	Problem	Language	Result	Execution time	Memory
700854		primenumber_zz	Game (IOI14_game)	C++14	15 / 100	1 ms	384 KiB

game

#include<bits/stdc++.h>
using namespace std;

int N;
int cnt,res;
vector<int>road[1515];

struct UnionFind {
    vector<int>par,size,cnt;
    vector<vector<int>>cld;
    UnionFind() {};
    UnionFind(int n) {
        par.resize(n);
        size.resize(n,1);
        cnt.resize(n);
        cld.resize(n);
        for(int i = 0; i < n; i++) {
            par[i] = i;
            cld[i].push_back(i);
        }
    }
    int find(int x) {
        if(par[x] == x) {
            return x;
        }
        return par[x] = find(par[x]);
    }
    bool same(int u,int v) {
        u = find(u);
        v = find(v);
        return (u == v);
    }
    void unite(int u,int v) {
        u = find(u);
        v = find(v);
        if(u == v) return;
        if(size[u] > size[v]) swap(u,v);
        for(int i:cld[u]) {
            cld[v].push_back(i);
            for(int j:road[i]) {
                if(!same(i,j) && same(j,v)) {
                    cnt[v] -= 2;
                }
            }
        }
        par[u] = v;
        size[v] += size[u];
        cnt[v] += cnt[u];
    }
    int consize(int x) {
        x = find(x);
        return size[x];
    }
    int concnt(int x) {
        x = find(x);
        return cnt[x];
    }
};

UnionFind uf;

void initialize(int n) {
    N = n;
    cnt = 0;
    res = n-1;
    UnionFind init(n);
    uf = init;
}

int hasEdge(int u, int v){
    if(uf.same(u,v)) {
        cnt++;
        return 0;
    }
    int a = uf.consize(u);
    int b = uf.concnt(u);
    if(a*(N-a) == b+1) {
        uf.unite(u,v);
        res--;
        return 1;
    }
    a = uf.consize(v);
    b = uf.concnt(v);
    if(a*(N-a) == b+1) {
        uf.unite(u,v);
        res--;
        return 1;
    }
    if(N*(N-1)/2-cnt == res) {
        res--;
        uf.unite(u,v);
        return 1;
    }
    uf.cnt[uf.find(u)]++;
    uf.cnt[uf.find(v)]++;
    cnt++;
    return 0;
}

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