Submission #1169632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169632		primenumber_zz	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	19 ms	3144 KiB

Joi

#include "Joi.h"
#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <class S> using pq = priority_queue<S,vector<S>,greater<S>>;
template <class S,class T> inline bool chmax(S &a,const T&b) { return (a < b)?a=b,1:0; }
template <class S,class T> inline bool chmin(S &a,const T&b) { return (a > b)?a=b,1:0; }

#define overlord3(_a,_b,_c,_d,name,...) name
#define REP1(i,n) for(ll i = 0; i < (n); i++) 
#define REP2(i,a,b) for(ll i = (a); i < (b); i++) 
#define REP3(i,a,b,c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overlord3(__VA_ARGS__,REP3,REP2,REP1)(__VA_ARGS__)
#define PER1(i,n) for(ll i = (n)-1; i >= 0; i--)
#define PER2(i,a,b) for(ll i = (a)-1; i >= b; i--)
#define PER3(i,a,b,c) for(ll i = (a)-1; i >= b; i -= c)
#define per(...) overlord3(__VA_ARGS__,PER3,PER2,PER1)(__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
#define si(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define lb(c,x) distance((c).begin(),lower_bound(all(c),x))
#define ub(c,x) distance((c).begin(),upper_bound(all(c),x))
#define SORT(c) sort(all(c))
#define REV(c) reverse(all(c))
#define UNIQUE(c) SORT(c),c.erase(unique(all(c)),c.end())

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    vvc<int>road(N);
    rep(i,M) {
        road[A[i]].pb(B[i]);
        road[B[i]].pb(A[i]);
    }
    vvc<int>ki1(N);
    vvc<int>ki2(N);
    {
        vc<int>used(N);
        auto dfs = [&](auto &dfs,int n) -> void {
            used[n] = 1;
            for(auto i:road[n]) {
                if(!used[i]) {
                    ki1[n].pb(i);
                    ki2[n].pb(i);
                    ki2[n].pb(i);
                    dfs(dfs,i);
                }
            }
        };
        dfs(dfs,0);
    }
    vc<int>f(N);
    {
        auto dfs = [&](auto &dfs,int n) -> int {
            int res = 1;
            for(auto i:ki1[n]) {
                res += dfs(dfs,i);
            }
            if(res >= 60) {
                f[n] = 1;
                return 0;
            }
            else {
                return res;
            }
        };
        dfs(dfs,0);
    }
    vc<int>dist(N,-1),used(N);
    queue<int>que;
    rep(i,N) {
        if(f[i]) {
            dist[i] = 0;
            que.push(i);
        }
    }
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        for(auto i:ki2[x]) {
            if(dist[i] == -1) {
                dist[i] = dist[x]+1;
                que.push(i);
            }
        }
    }
    vc<int>col(N);
    rep(i,N) {
        if(!f[i]) continue;
        vc<int>id;
        auto dfs = [&](auto &dfs,int n) -> void {
            id.pb(n);
            for(auto i:ki1[n]) {
                if(f[i]) continue;
                dfs(dfs,i);
            }
        };
        dfs(dfs,i);
        rep(j,60) {
            used[id[j]] = 1;
            col[id[j]] = 1 & (X >> j);
        }
    }
    rep(i,N) {
        if(!used[i]) {
            col[i] = 1 & (X >> (60-dist[i]));
        }
        MessageBoard(i,col[i]);
    }
}

Ioi

#include "Ioi.h"
#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <class S> using pq = priority_queue<S,vector<S>,greater<S>>;
template <class S,class T> inline bool chmax(S &a,const T&b) { return (a < b)?a=b,1:0; }
template <class S,class T> inline bool chmin(S &a,const T&b) { return (a > b)?a=b,1:0; }

#define overlord3(_a,_b,_c,_d,name,...) name
#define REP1(i,n) for(ll i = 0; i < (n); i++) 
#define REP2(i,a,b) for(ll i = (a); i < (b); i++) 
#define REP3(i,a,b,c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overlord3(__VA_ARGS__,REP3,REP2,REP1)(__VA_ARGS__)
#define PER1(i,n) for(ll i = (n)-1; i >= 0; i--)
#define PER2(i,a,b) for(ll i = (a)-1; i >= b; i--)
#define PER3(i,a,b,c) for(ll i = (a)-1; i >= b; i -= c)
#define per(...) overlord3(__VA_ARGS__,PER3,PER2,PER1)(__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
#define si(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define lb(c,x) distance((c).begin(),lower_bound(all(c),x))
#define ub(c,x) distance((c).begin(),upper_bound(all(c),x))
#define SORT(c) sort(all(c))
#define REV(c) reverse(all(c))
#define UNIQUE(c) SORT(c),c.erase(unique(all(c)),c.end())

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    vvc<int>road(N);
    rep(i,M) {
        road[A[i]].pb(B[i]);
        road[B[i]].pb(A[i]);
    }
    vc<int>pa(N);
    vvc<int>ki1(N);
    vvc<int>ki2(N);
    {
        vc<int>used(N);
        auto dfs = [&](auto &dfs,int n) -> void {
            used[n] = 1;
            for(auto i:road[n]) {
                if(!used[i]) {
                    ki1[n].pb(i);
                    ki2[n].pb(i);
                    ki2[i].pb(n);
                    pa[i] = n;
                    dfs(dfs,i);
                }
            }
        };
        dfs(dfs,0);
    }
    vc<int>f(N);
    {
        auto dfs = [&](auto &dfs,int n) -> int {
            int res = 1;
            for(auto i:ki1[n]) {
                res += dfs(dfs,i);
            }
            if(res >= 60) {
                f[n] = 1;
                return 0;
            }
            else {
                return res;
            }
        };
        dfs(dfs,0);
    }
    ll ans = 0;
    int now1 = P,now2 = V;
    int lim = 59;
    {
        vc<int>col(N);
        rep(i,N) {
            if(!f[i]) continue;
            vc<int>id;
            auto dfs = [&](auto &dfs,int n) -> void {
                id.pb(n);
                for(auto i:ki1[n]) {
                    if(f[i]) continue;
                    dfs(dfs,i);
                }
            };
            dfs(dfs,i);
            rep(j,60) {
                col[id[j]] = 1;
            }
        }
        vc<int>dist(N,-1);
        queue<int>que;
        rep(i,N) {
            if(col[i]) {
                dist[i] = 0;
                que.push(i);
            }
        }
        while(!que.empty()) {
            int x = que.front();
            que.pop();
            for(auto i:ki2[x]) {
                if(dist[i] == -1) {
                    dist[i] = dist[x]+1;
                    que.push(i);
                }
            }
        }
        vc<int>res;
        que.push(P);
        while(!que.empty()) {
            int x = que.front();
            que.pop();
            res.pb(x);
            for(auto i:ki2[x]) {
                if(dist[i] == dist[x]-1) {
                    que.push(i);
                    break;
                }
            }
        }
        rep(i,si(res)) {
            if(i) {
                now1 = res[i];
                now2 = Move(res[i]);
            }
            if(i+1 == si(res)) break;
            ans |= (1ll << (59-i))*now2;
            lim--;
        }
    }
    {
        int now = now1;
        while(!f[now]) {
            now = pa[now];
        }
        vc<int>num(N,-1),used(N);
        vc<int>id;
        auto dfs = [&](auto &dfs,int n) -> void {
            id.pb(n);
            for(auto i:ki1[n]) {
                if(f[i]) continue;
                dfs(dfs,i);
            }
        };
        dfs(dfs,now);
        rep(j,60) {
            num[id[j]] = j;
        }
        while(true) {
            auto dfs2 = [&](auto &dfs2,int n) -> void {
                used[n] = 1;
                ans |= (1ll << num[n])*now2;
                for(auto i:ki1[n]) {
                    if(num[i] == -1) continue;
                    if(num[i] > lim) continue;
                    if(used[i]) continue;
                    now1 = i;
                    now2 = Move(i);
                    dfs2(dfs2,i);
                    now1 = n;
                    now2 = Move(n);
                }
            };
            dfs2(dfs2,now1);
            if(now1 == now) break;
            now1 = pa[now1];
            now2 = Move(now1);
        }
    }
    return ans;
}

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