Submission #241294

#	Time	Username	Problem	Language	Result	Execution time	Memory
241294		Mercenary	Game (IOI14_game)	C++14	100 / 100	527 ms	18040 KiB

game

//#include "crocodile.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1500 + 5;
const int logn = log2(maxn) + 1;
int a[maxn][maxn] , lab[maxn];
int FindLab(int u){return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);}
int N;

void Merge(int u , int v){
    u = FindLab(u);v = FindLab(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u,v);
    lab[u] += lab[v];
    lab[v] = u;
    for(int i = 0 ; i < N ; ++i){
        a[u][i] += a[v][i];
        a[i][u] = a[u][i];
    }
}
void initialize(int n){
    N = n;
    fill_n(lab,n + 1 , -1);
}
int hasEdge(int u, int v){
    u = FindLab(u);v = FindLab(v);
    if(u == v)return 1;
    ++a[u][v];++a[v][u];
    if(a[u][v] == lab[u] * lab[v])return Merge(u , v) , 1;
    return 0;
};

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