Submission #362811

#	Time	Username	Problem	Language	Result	Execution time	Memory
362811		denkendoemeer	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	28 ms	6328 KiB

Joi

#include<bits/stdc++.h>
#include "Joi.h"
#define ll long long
using namespace std;
vector<int>g[20005];
int tin[20005],u=0;
bool viz[200005];
void dfs(int nod,ll x)
{
    viz[nod]=1;
    tin[nod]=u++;
    int num=tin[nod]%60;
    MessageBoard(nod,(x>>num)&1);
    for(auto it:g[nod]){
        if (viz[it]==0)
            dfs(it,x);
    }
}
void Joi(int n,int m,int a[],int b[],ll x,int t)
{
    int i;
    for(i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0,x);
}

Ioi

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#include "Ioi.h"
vector<int>g[20005];
int tin[20005],cnt[20005],t[20005],u=0,v[60],ans[20005],h[20005];
bool viz[20005],w[20005];
vector<int>tree[20005];
void dfs(int nod)
{
    viz[nod]=1;
    cnt[nod]=1;
    tin[nod]=u++;
    for(auto it:g[nod]){
        if (viz[it]==0){
            dfs(it);
            t[it]=nod;
            tree[nod].push_back(it);
            cnt[nod]+=cnt[it];
        }
    }
}
int cur;
void dfs2(int nod,int ta)
{
    if (cur==60)
        return ;
    ++cur;
    int num=tin[nod]%60;
    w[nod]=v[num]==-1;
    h[nod]=0;
    for(auto it:tree[nod]){
        dfs2(it,nod);
        w[nod]|=w[it];
        h[nod]=max(h[nod],h[it]+1);
    }
}
void dfs3(int nod,int tat,bool oki)
{
    if (tree[nod].empty())
        return ;
    int maxi=-1;
    for(auto it:tree[nod]){
        if (w[it]){
            if (maxi==-1 || h[maxi]<h[it])
                maxi=it;
        }
    }
    if (oki && maxi!=-1){
        for(auto it:tree[nod]){
            if (w[it] && it!=maxi){
                v[tin[it]%60]=it;
                ans[it]=Move(it);
                dfs3(it,nod,0);
                Move(nod);
            }
        }
        v[tin[maxi]%60]=maxi;
        ans[maxi]=Move(maxi);
        dfs3(maxi,nod,1);
    }
    else{
        for(auto it:tree[nod]){
            if (w[it]){
                v[tin[it]%60]=it;
                ans[it]=Move(it);
                dfs3(it,nod,0);
                Move(nod);
            }
        }
    }
}
ll Ioi(int n,int m,int a[],int b[],int x,int y,int st)
{
    int i;
    for(i=0;i<60;i++)
        v[i]=-1;
    for(i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0);
    ans[x]=y;
    v[tin[x]%60]=x;
    while(cnt[x]<60){
        x=t[x];
        ans[x]=Move(x);
        v[tin[x]%60]=x;
    }
    dfs2(x,t[x]);
    if (w[x])
        dfs3(x,t[x],1);
    ll rez=0;
    for(i=0;i<60;i++)
        rez=rez+(1LL<<i)*ans[v[i]];
    return rez;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17