Submission #1262084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262084		motion	Game (IOI14_game)	C++20	42 / 100	128 ms	13640 KiB

game

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> p,s;
vector<map<int,int>> vec;

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

void unite(int x,int y)
{
    int rx=FIND(x),ry=FIND(y);
    if(s[rx]<s[ry]) swap(rx,ry);
    s[rx]+=s[ry];
    p[ry]=rx;
    for(int i=0;i<n;i++)
    {
        if(i==rx || i==ry) continue;
        vec[i][rx]+=vec[i][ry];
    }
    for(auto [key,val]:vec[rx])
    {
        vec[rx][key]+=vec[ry][key];
    }

}

int hasEdge(int u,int v)
{
    int ru=FIND(u),rv=FIND(v);
    if(vec[ru][rv]==s[rv]*s[ru]-1)
    {
        unite(ru,rv);
        return 1;
    }
    else
    {
        vec[ru][rv]++;
        vec[rv][ru]++;
        return 0;
    }
}

void initialize(int k)
{
    n=k;
    s=vector<int>(n,1);
    vec=vector<map<int,int>>(n);
    for(int i=0;i<n;i++)
    {
        p.push_back(i);
    }
}

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