Submission #18111

#	Time	Username	Problem	Language	Result	Execution time	Memory
18111		chan492811	Game (IOI14_game)	C++98	100 / 100	455 ms	9964 KiB

game

#include <cstring>
#include <algorithm>
using namespace std;
struct data{
    int l,r,edge;
};
data tree[8000];
int tn,n,flag;
void make_tree(int a){
    if(a>=tn) return;
    make_tree(a*2); make_tree(a*2+1);
    if(tree[a*2].l==-1) return;
    else if(tree[a*2+1].l==-1){ tree[a]=tree[a*2]; return; }
    tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r; tree[a].edge=(tree[a*2].r-tree[a*2].l+1)*(tree[a*2+1].r-tree[a*2+1].l+1);
}
void initialize(int N){
    int i;
    n=N; tn=1;
    memset(tree,-1,sizeof(tree));
    while(tn<n) tn*=2;
    for(i=tn;i<tn+n;i++) tree[i].l=i-tn,tree[i].r=i-tn;
    make_tree(1);
}
int islink(int a,int u,int v){
    int res;
    if(tree[a].r==tree[a].l) return 0;
    if(tree[a].l<=u && tree[a].r>=v){
        res=islink(a*2,u,v)+islink(a*2+1,u,v);
        if(res>0) return 1;
        if(tree[a].edge==1){ flag=1; return 1; }
        tree[a].edge--; flag=0; return 1;
    }
    else return 0;
}
int hasEdge(int u, int v){
    if(u>v) swap(u,v);
    int a=islink(1,u,v);
    return flag;
    return 0;
}

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