Submission #345115

#	Time	Username	Problem	Language	Result	Execution time	Memory
345115		rrrr10000	Game (IOI14_game)	C++14	100 / 100	684 ms	34124 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define dame(a) {cout<<a<<endl;return 0;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vvvp=vector<vvp>;
using vb=vector<bool>;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
vvi g;
int n;
class UF{
public:
    vi data;stack<P> st;
    UF(ll N){
        data=vi(N,1);
    }
    bool heigou(ll x,ll y,bool undo=false){
        x=root(x);y=root(y);
        if(data[x]>data[y])swap(x,y);
        if(undo){st.emplace(y,data[y]);st.emplace(x,data[x]);}
        if(x==y)return false;
        rep(i,n)if(root(i)==i){
            g[i][y]+=g[i][x];
            g[y][i]+=g[i][x];
        }
        data[y]+=data[x];data[x]=-y;
        return true;
    }
    ll root(ll i){if(data[i]>0)return i;return root(-data[i]);}
    ll getsize(ll i){return data[root(i)];}
    bool same(ll a,ll b){return root(a)==root(b);}
    void undo(){rep(i,2){data[st.top().fi]=st.top().se;st.pop();}}
};
UF uf(0);
void initialize(int N){
    n=N;g=vvi(n,vi(n));uf=UF(n);
}
int hasEdge(int a,int b){
    a=uf.root(a);b=uf.root(b);
    if(g[a][b]==uf.getsize(a)*uf.getsize(b)-1){
        uf.heigou(a,b);return 1;
    }
    else{
        g[a][b]++;g[b][a]++;return 0;
    }
}
/*
int main(){
    ll n;cin>>n;
    initialize(n);
    rep(i,n*(n-1)/2){
        ll a,b;cin>>a>>b;
        out(hasEdge(a,b));
    }
}*/

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