Submission #709341

#	Time	Username	Problem	Language	Result	Execution time	Memory
709341		Antekb	Amusement Park (JOI17_amusement_park)	C++17	82 / 100	38 ms	5700 KiB

Joi

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug2(){cerr<<"\n";}
template<typename H, typename... T>
void debug2(H h, T... t){
  cerr<<h;
  if(sizeof...(t))cerr<<", ";
  debug2(t...);
}
#define deb(x) cerr<<#x<<" = ";debug2(x);
mt19937 rng2(chrono::high_resolution_clock().now().time_since_epoch().count());
const int NN2=1e4+5;
#include "Joi.h"

vector<int> bit2;
vi E2[NN2];
int reszta2;
int vis2[NN2], czy2[NN2], kol2[NN2];
vector<pii> todo2;
int ddfs2(int v){
    int m=0;
    vis2[v]=2;
    for(int u:E2[v]){
        if(czy2[u] && vis2[u]!=2){
            m=max(m, ddfs2(u));
        }
    }
    m++;
    todo2.eb(-m, v);
    return m;
}
vi ddfs(int v){
    vi V;
    vis2[v]=1;
    for(int u:E2[v]){
        if(!vis2[u]){
            vi V2=ddfs(u);
            for(int i:V2)V.pb(i);
        }
    }
    czy2[v]=1;
    V.pb(v);
    if(v==0 || (reszta2-V.size()>=60 && V.size()>=60)){
        for(int i:V)czy2[i]=1;
        ddfs2(v);
        sort(all(todo2));
        for(int i=0; i<60; i++)kol2[todo2[i].nd]=i;
        for(pii i:todo2)czy2[i.nd]=0, vis2[i.nd]=1;
        V.clear();
        reszta2-=todo2.size();
        todo2.clear();
    }
    return V;
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
    reszta2=n;
    for(int i=0; i<m; i++){
        E2[A[i]].pb(B[i]);
        E2[B[i]].pb(A[i]);
    }
    for(int i=0; i<60; i++)bit2.pb(X&1), X/=2;
    ddfs(0);
    for(int i=0; i<n; i++){
        MessageBoard(i, bit2[kol2[i]]);
    }
}

Ioi

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
  cerr<<h;
  if(sizeof...(t))cerr<<", ";
  debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int NN=1e4+5, INF=1e9+5;
#include "Ioi.h"

int bit[60];
int reszta;
vi E[NN];
int vis[NN], czy[NN], kol[NN], par[NN];
vector<pii> todo;
int pp;
int dfs2(int v){
    int m=0;
    vis[v]=2;
    for(int u:E[v]){
        if(czy[u] && vis[u]!=2){
            m=max(m, dfs2(u));
        }
    }
    m++;
    todo.eb(-m, v);
    return m;
}
void move(int x){
    int t=Move(x);
    bit[kol[x]]=t;
}
void dfs3(int v){
    deb(v, kol[v]);
    vis[v]=2;
    for(int u:E[v]){
        if(vis[u]==3){
            move(u);
            dfs3(u);
            move(v);
        }
    }
}
vector<int> dfs(int v){
    vis[v]=1;
    vi V;
    for(int u:E[v]){
        if(!vis[u]){
            par[u]=v;
            vi V2=dfs(u);
            for(int i:V2)V.pb(i);
        }
    }
    //deb(v, 1);
    if(v==200){
        deb();
        deb();
        deb();
    }
    V.pb(v);
    if(v==0 || (reszta-V.size()>=60 && V.size()>=60)){
        deb(v, V.size());
        for(int i:V)czy[i]=1;
        dfs2(v);
        sort(all(todo));
        for(pii &i:todo){
            if(i.nd==200){
                deb(i.st, i.nd, czy[200], pp)
            }
        }
        for(int i=0; i<60; i++)kol[todo[i].nd]=i, vis[todo[i].nd]=3;
        if(czy[pp]){
            deb(5, v);
            while(vis[pp]!=3){
                deb(pp, par[pp]);
                move(par[pp]), pp=par[pp];
            }
            deb(5);
            dfs3(pp);
            pp=1e4;
        }
        for(pii i:todo)czy[i.nd]=0, vis[i.nd]=1;
        V.clear();
        reszta-=todo.size();
        todo.clear();
    }
    return V;
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    reszta=n;
    for(int i=0; i<m; i++){
        E[A[i]].pb(B[i]);
        E[B[i]].pb(A[i]);
    }
    pp=P;
    dfs(0);
    bit[kol[P]]=V;
    ll x=0;
    for(int i=59; i>=0; i--)x=x+x+bit[i];
        deb(x);
    return x;
}

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