제출 #1157464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157464		jerzyk	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	17 ms	2648 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;

namespace A
{

const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 10'007;
const int K = 60;
bool vis[N], czy[N];
int sum[N];

int il[N];

vector<int> ed[N];

int wzo[K + 10];
int ans[N];

bool Cp(int a, int b)
{
    return (il[a] > il[b]);
}

void DFSB(int v, int dd)
{
    vis[v] = 1;
    dd %= K;
    if(dd == 0)
        czy[v] = 1;

    sum[v] = 1; il[v] = 1;
    vector<int> nw;
    sort(ed[v].begin(), ed[v].end());
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(vis[ed[v][i]]) continue;
        DFSB(ed[v][i], dd + 1);
        il[v] = max(il[v], il[ed[v][i]] + 1);
        sum[v] += sum[ed[v][i]];
        if(!czy[ed[v][i]])
            nw.pb(ed[v][i]);
    }
    sort(nw.begin(), nw.end(), Cp);
    ed[v] = nw;
    //cerr << "DFS1 " << v << " " << sum[v] << " " << K << "\n";
    if(sum[v] < K && czy[v])
        czy[v] = 0;
    if(czy[v])
    {
        il[v] = 0;
        sum[v] = 0;
    }
}

void DFSS(int v, int &cnt)
{
    //cerr << "DFS Set " << v << " " << cnt << "\n";
    ans[v] = wzo[cnt]; ++cnt;
    int beg = cnt;
    if(cnt >= K) return;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(cnt < K)
            DFSS(ed[v][i], cnt);
        else if(il[ed[v][i]] >= K - beg)
        {
            int a = beg;
            DFSS(ed[v][i], a);
        }
    }
}

}

void Joi(int _N, int _M, int A[], int B[], long long _X, int _T)
{
    using namespace A;
    int n = _N, m = _M;
    for(int i = 0; i < m; ++i)
    {
        ed[A[i]].pb(B[i]);
        ed[B[i]].pb(A[i]);
    }
    for(int i = 0; i < K; ++i)
        wzo[i] = (bool)((1LL<<(ll)i) & _X);
    DFSB(0, 0);
    int cnt;
    for(int i = 0; i < n; ++i)
    {
        if(!czy[i]) continue;
        cnt = 0;
        DFSS(i, cnt);
    }
    for(int i = 0; i < n; ++i)
        MessageBoard(i, ans[i]);
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;

namespace B
{
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 10'007;
const int K = 60;

bool vis[N], czy[N];
int sum[N], oj[N];

int il[N];

vector<int> ed[N];

int val[N];
int pos[N];
ll answer = 0LL;

bool Cp(int a, int b)
{
    return (il[a] > il[b]);
}

void DFSB(int v, int dd)
{
    vis[v] = 1;
    dd %= K;
    if(dd == 0)
        czy[v] = 1;

    sum[v] = 1; il[v] = 1;
    vector<int> nw;
    sort(ed[v].begin(), ed[v].end());
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(vis[ed[v][i]]) continue;
        oj[ed[v][i]] = v;
        DFSB(ed[v][i], dd + 1);
        il[v] = max(il[v], il[ed[v][i]] + 1);
        sum[v] += sum[ed[v][i]];
        if(!czy[ed[v][i]])
            nw.pb(ed[v][i]);
    }
    sort(nw.begin(), nw.end(), Cp);
    ed[v] = nw;
    if(sum[v] < K && czy[v])
        czy[v] = 0;
    if(czy[v])
    {
        il[v] = 0;
        sum[v] = 0;
    }
}

void DFS2(int v, int &cnt)
{
    //cerr << "DFS2 Pos: " << v << " " << cnt << "\n";
    pos[v] = cnt + 1;
    if(cnt >= K) return;
    ++cnt;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        DFS2(ed[v][i], cnt);
        if(cnt >= K) return;
    }
}

void DFSA(int v, int a, bool r)
{
    answer += (1LL<<((ll)pos[v] - 1LL)) * (ll)a;
    for(int i = (int)ed[v].size() - 1; i >= 0; --i)
    {
        if(pos[ed[v][i]] > 0)
        {
            int dd = Move(ed[v][i]);
            DFSA(ed[v][i], dd, ((i != 0) | r));
        }
    }
    if(r)
    {
        Move(oj[v]);
    }
}

}

long long Ioi(int _N, int _M, int A[], int B[], int P, int V, int T)
{
    using namespace B;
    //int n = _N;
    int m = _M;
    for(int i = 0; i < m; ++i)
    {
        ed[A[i]].pb(B[i]);
        ed[B[i]].pb(A[i]);
    }
    DFSB(0, 0);
    vector<int> pth;
    val[P] = V;
    while(!czy[P])
    {
        pth.pb(P);
        val[oj[P]] = Move(oj[P]);
        P = oj[P];
    }
    pth.pb(P);
    reverse(pth.begin(), pth.end());
    if((int)pth.size() >= K)
    {
        ll ans = 0LL;
        for(int i = 0; i < K; ++i)
            ans += (1LL<<(ll)i) * val[pth[i]];
        return ans;
    }
    int cnt = 0;
    DFS2(P, cnt);
    DFSA(P, val[P], 0);
    return answer;
}

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