Submission #1169590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169590		primenumber_zz	Amusement Park (JOI17_amusement_park)	C++20	28 / 100	17 ms	2632 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>ki(N);
    {
        vc<int>used(N);
        auto dfs = [&](auto &dfs,int n) -> void {
            used[n] = 1;
            for(auto i:road[n]) {
                if(!used[i]) {
                    ki[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:ki[n]) {
                res += dfs(dfs,i);
            }
            if(res >= 60) {
                f[n] = 1;
                return 0;
            }
            else {
                return res;
            }
        };
        dfs(dfs,0);
    }
    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:ki[n]) {
                if(f[i]) continue;
                dfs(dfs,i);
            }
        };
        dfs(dfs,i);
        rep(j,60) {
            col[id[j]] = 1 & (X >> j);
        }
    }
    rep(i,N) {
        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]);
    }
    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);
                    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);
    }
    int now1 = P,now2 = V;
    {
        vc<int>dist(N,-1);
        dist[P] = 0;
        queue<int>que;
        que.push(P);
        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);
                }
            }
        }
        int mi = -1;
        rep(i,N) {
            if(f[i]) {
                if(mi == -1) mi = i;
                else if(dist[mi] > dist[i]) mi = i;
            }
        }
        vc<int>res;
        que.push(mi);
        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;
                }
            }
        }
        REV(res);
        rep(i,1,si(res)) {
            now1 = res[i];
            now2 = Move(res[i]);
        }
    }
    ll ans = now2;
    int cnt = 0;
    auto dfs = [&](auto &dfs,int n) -> void {
        if(cnt == 60) return;
        ans |= (1ll << cnt)*now2;
        cnt++;
        if(cnt == 60) return;
        for(auto i:ki1[n]) {
            if(f[i]) continue;
            now1 = i;
            now2 = Move(i);
            dfs(dfs,i);
            now1 = n;
            now2 = Move(n);
        }
    };
    dfs(dfs,now1);
    return ans;
}

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