Submission #1092062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092062		codexistent	Game (IOI14_game)	C++14	42 / 100	890 ms	97104 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)

int p[1005];
set<pair<int, int>> adj[1005];
set<pair<int, int>> edge[1005][1005];

int find(int x){
    return (p[x] == x) ? x : (p[x] = find(p[x]));
}

void onion(int a, int b){
    a = find(a), b = find(b);
    if(a == b) return;

    if(adj[a].size() < adj[b].size()) swap(a, b);

    for(auto i : adj[b]){
        adj[a].insert(i);
        int x = find(i.first), y = find(i.second);
        if(y == b) swap(x, y);

        edge[min(a, y)][max(a, y)].insert(i);
        edge[min(b, y)][max(b, y)].erase(i);
        // cout << " WE ONLY MERGED EDGE " << i.first << " TO " << i.second << ", ERASED FROM " << b << ", " << y << " AND ADDED TO " << a << ", " << y << endl;
    }
    adj[b].clear();

    p[a] = p[b] = a; 
}

void initialize(int n) {
    FOR(i, 0, n - 1) p[i] = i;

    FOR(i, 0, n - 1){
        FOR(j, i + 1, n - 1){
            adj[i].insert(make_pair(i, j));
            adj[j].insert(make_pair(i, j));
            edge[i][j].insert(make_pair(i, j));
        }
    }
}

int hasEdge(int u, int v) {
    pair<int, int> e = make_pair(min(u, v), max(u, v));

    u = find(u), v = find(v);
    if(u == v) return 1;

    adj[u].erase(e);
    adj[v].erase(e);
    edge[min(u, v)][max(u, v)].erase(e);
    if(edge[min(u, v)][max(u, v)].size() == 0){
        onion(u, v);
        return 1;
    }
    return 0;
}

/*int main(){
    int x; cin >> x;
    initialize(x);

    FOR(i, 1, (x * (x - 1)) / 2){
        int a, b;
        cin >> a >> b;

        bool res = hasEdge(a, b);

        if(res){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }

        FOR(j, 0, x - 1){
            FOR(k, j + 1, x - 1){
                cout << "ADJ MATRIX FOR " << j << " TO " << k << " HAS EDGES " << endl;
                for(auto i : edge[j][k]){
                    cout << i.first << " " << i.second << endl;
                }
            }
        }
    }
}*/

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