Submission #1146282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146282		_8_8_	Amusement Park (JOI17_amusement_park)	C++20	82 / 100	18 ms	6984 KiB

Joi

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

using namespace std;

typedef long long ll;

const int N = (int)1e5 + 12, b = 60;

mt19937 rng1(123321);
vector<int> g1[N];
int tin1[N], timer1;
bool vis1[N];
ll x;
void dfs1(int v) {
    tin1[v] = timer1++;
    vis1[v] = 1;
    MessageBoard(v, ((x >> (tin1[v] % 60)) & 1));
    for(int to : g1[v]) {
        if(!vis1[to]) {
            dfs1(to);
        }        
    }
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
    x = X;
    for(int i = 0; i < m; i++) {
        g1[A[i]].push_back(B[i]);
        g1[B[i]].push_back(A[i]);
    }
    for(int i = 0; i < n; i++) {
        sort(g1[i].begin(), g1[i].end());
    }
    dfs1(32);
}

Ioi

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

using namespace std;
typedef long long ll;

const int N = (int)1e5 + 12, b = 60;

mt19937 rng(123321);
ll d[N], mxd[N], pr[N], timer, sz[N];
vector<int> g[N], G[N];
int tin[N], bt[N], tout[N];
bool vis[N];
void dfs(int v) {
    tin[v] = timer++;
    tin[v] %= 60;
    vis[v] = 1;
    sz[v] = 1;
    for(int to : g[v]) {
        if(!vis[to]) {
            pr[to] = v;
            dfs(to);
            sz[v] += sz[to];
            G[v].push_back(to);
        }        
    }
    tout[v] = timer;
    tout[v] %= b;
}

ll ans = 0;
bool check() {
    bool ret = true;
    for(int i = 0; i < b; i++) {
        if(bt[i] == -1) ret = false;
    }
    return ret;
}
bool ok = 1;
void go(int v, int val) {
    bt[tin[v]] = val;
    vis[v] = 1;
    if(check()) {
        return;
    }
    for(int to : G[v]) {
        if(!vis[to]) {
            bool ok = 1;
            for(int j = min(tin[to], tout[to]); j <= max(tin[to], tout[to]); j++) {
                if(bt[j] == -1) {
                    ok = 0;
                }
            }
            if(ok) continue;
            go(to, Move(to));
            if(check()) return;
        }
    }
    go(pr[v], Move(pr[v]));
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    for(int i = 0; i < m; i++) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    for(int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
    }
    dfs(32);
    for(int i = 0; i < b; ++i) {
        bt[i] = -1;
    }
    for(int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    go(P, V);
    for(int i = 0; i < b; i++) {
        if(bt[i]) {
            ans += (1ll << i);
        }
    }
    return ans;
}

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