Submission #520818

#	Time	Username	Problem	Language	Result	Execution time	Memory
520818		tengiz05	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	38 ms	6892 KiB

Joi

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

using i64 = long long;
using namespace std;

namespace joi {
    const int MAX_BIT = 60;
    int n;
    vector<vector<int>> e, adj;
    vector<bool> vis;
    void dfs(int u) {
        vis[u] = true;
        for (int v : adj[u]) {
            if (!vis[v]) {
                e[u].push_back(v);
                e[v].push_back(u);
                dfs(v);
            }
        }
    }
    int cnt = 0;
    set<int> s;
    vector<set<int>> f;
    vector<int> val(n);
    void find(int u, int p) {
        val[u] = cnt++;
        if (cnt == MAX_BIT) {
            return;
        }
        for (int v : e[u]) {
            if (v != p) {
                f[u].insert(v);
                f[v].insert(u);
                find(v, u);
                if (cnt == MAX_BIT)
                    return;
            }
        }
    }
    void mark(int u, int p) {
        bool in = false, op1 = false, op2 = false;
        int x = -1, to = -1;
        if (val[u] == -1) {
            in = true;
            auto t = s.begin();
            if (*t == p) t++;
            x = *t;
            to = *f[x].begin();
            s.erase(x);
            f[x].erase(to);
            f[to].erase(x);
            if (f[to].size() == 1) {
                op1 = true;
                s.insert(to);
            }
            if (f[p].size() == 1) {
                op2 = true;
                s.erase(p);
            }
            f[p].insert(u);
            f[u].insert(p);
            s.insert(u);
            val[u] = val[x];
        }
        for (int v : e[u]) {
            if (v != p) {
                mark(v, u);
            }
        }
        if (in) {
            s.erase(u);
            f[p].erase(u);
            f[u].erase(p);
            if (op2) {
                s.insert(p);
            }
            if (op1) {
                s.erase(to);
            }
            f[x].insert(to);
            f[to].insert(x);
            s.insert(x);
        }
    }
};
using namespace joi;

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    n = N;
    adj.resize(n);
    e.resize(n);
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    vis.assign(n, 0);
    dfs(0);
    
    f.resize(n);
    val.resize(n, -1);
    find(0, -1);
    
    for (int i = 0; i < n; i++) {
        if (f[i].size() == 1) {
            s.insert(i);
        }
    }
    
    mark(0, -1);
    
    for (int i = 0; i < n; i++) {
        assert(val[i] != -1);
        MessageBoard(i, X >> val[i] & 1);
    }
}

Ioi

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

using i64 = long long;
using namespace std;

namespace ioi {
    const int MAX_BIT = 60;
    int n;
    vector<vector<int>> e, adj;
    vector<bool> vis;
    void dfs(int u) {
        vis[u] = true;
        for (int v : adj[u]) {
            if (!vis[v]) {
                e[u].push_back(v);
                e[v].push_back(u);
                dfs(v);
            }
        }
    }
    int cnt = 0;
    set<int> s;
    vector<set<int>> f;
    vector<int> val(n);
    void find(int u, int p) {
        val[u] = cnt++;
        if (cnt == MAX_BIT) {
            return;
        }
        for (int v : e[u]) {
            if (v != p) {
                f[u].insert(v);
                f[v].insert(u);
                find(v, u);
                if (cnt == MAX_BIT)
                    return;
            }
        }
    }
    void mark(int u, int p) {
        bool in = false, op1 = false, op2 = false;
        int x = -1, to = -1;
        if (val[u] == -1) {
            in = true;
            auto t = s.begin();
            if (*t == p) t++;
            x = *t;
            to = *f[x].begin();
            s.erase(x);
            f[x].erase(to);
            f[to].erase(x);
            if (f[to].size() == 1) {
                op1 = true;
                s.insert(to);
            }
            if (f[p].size() == 1) {
                op2 = true;
                s.erase(p);
            }
            f[p].insert(u);
            f[u].insert(p);
            s.insert(u);
            val[u] = val[x];
        }
        for (int v : e[u]) {
            if (v != p) {
                mark(v, u);
            }
        }
        if (in) {
            s.erase(u);
            f[p].erase(u);
            f[u].erase(p);
            if (op2) {
                s.insert(p);
            }
            if (op1) {
                s.erase(to);
            }
            f[x].insert(to);
            f[to].insert(x);
            s.insert(x);
        }
    }
    vector<bool> h(MAX_BIT);
    i64 ans = 0;
    void get(int u) {
        for (int v : e[u]) {
            if (!h[val[v]]) {
                int x = Move(v);
                ans |= (1LL * x) << val[v];
                h[val[v]] = true;
                get(v);
                Move(u);
            }
        }
    }
};
using namespace ioi;
long long Ioi(int N, int M, int A[], int B[], int u, int V, int T) {
    n = N;
    adj.resize(n);
    e.resize(n);
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    vis.assign(n, 0);
    dfs(0);
    
    f.resize(n);
    val.resize(n, -1);
    find(0, -1);
    
    for (int i = 0; i < n; i++) {
        if (f[i].size() == 1) {
            s.insert(i);
        }
    }
    
    mark(0, -1);
    
    h[val[u]] = 0;
    ans = (1LL * V) << val[u];
    get(u);
    
    return ans;
}

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