Submission #107442

#	Time	Username	Problem	Language	Result	Execution time	Memory
107442		szawinis	Amusement Park (JOI17_amusement_park)	C++17	83 / 100	139 ms	5892 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+1;

struct Solver_Joi {
    int n, m, mxd, mxdv, color[N], last[N];
    long long X;
    vector<int> g1[N], g2[N];

    bool vis[N];
    int par[N], depth[N];
    void init_dfs(int u) {
        vis[u] = true;
        if(depth[u] > mxd) {
            mxd = depth[u];
            mxdv = u;
        }
        for(int v: g1[u]) {
            if(vis[v]) continue;
            g2[u].push_back(v);
            par[v] = u;
            depth[v] = depth[u] + 1;
            init_dfs(v);
        }
    }

    void colorBig(int u) {
        color[u] = depth[u] % 60;
        for(int v: g2[u]) {
            colorBig(v);
        }
    }

    int curr_count;
    int st[N];
    vector<int> ord;

    void prepColorSmall1(int u) {
        color[u] = (curr_count >= 60 ? -1 : curr_count);
        ++curr_count;

        if (color[u] != -1) {
            st[u] = ord.size();
            ord.push_back(u);
        }

        for (int v: g2[u]) {
            prepColorSmall1(v);
            if(color[u] != -1 && ord.back() != u) ord.push_back(u);
        }
    }

    void solve() {
        par[0] = -1;
        fill(color, color+N, -1);
        fill(last, last+N, -1);
        init_dfs(0);

        if(mxd >= 59) {
            colorBig(0);
            for(int i = 0; i < n; i++) {
                assert(color[i] != -1 && 0 <= color[i] && color[i] < 60);
                MessageBoard(i, X >> color[i] & 1);
            }
            return;
        }

        prepColorSmall1(0);
//        for(int x: ord) cerr << x << ' ';
//        cerr << endl;

        for(int i = 0; i < n; i++) {
            last[i] = i;
            while(color[last[i]] == -1) last[i] = par[last[i]];
        }

        for(int i = 0; i < n; i++) {
            if(color[i] != -1) continue;

            int idx = st[last[i]];
            int depth_diff = depth[i] - depth[last[i]];

            set<int> distinct_mods;
            while(distinct_mods.size() < 60 - depth_diff) {
                distinct_mods.insert(color[ord[idx]]);
                idx = (idx + 1) % ord.size();
            }

            for(int mod = 0; mod < 60; mod++) {
                if(!distinct_mods.count(mod)) {
                    color[i] = mod;
                    break;
                }
            }
            assert(ord[st[last[i]]] == last[i]);

//            cerr << i << ' ' << last[i] << ' ' << color[i] << endl;
        }

        for(int i = 0; i < n; i++) {
            assert(color[i] != -1 && 0 <= color[i] && color[i] < 60);
            MessageBoard(i, X >> color[i] & 1);
        }
    }

    Solver_Joi(int n, int m, long long X, int A[], int B[]): n(n), m(m), X(X) {
        for(int i = 0; i < m; i++) {
            g1[A[i]].push_back(B[i]);
            g1[B[i]].push_back(A[i]);
        }
    }
};

void Joi(int n, int m, int A[], int B[], long long X, int T) {
    Solver_Joi *solver = new Solver_Joi(n, m, X, A, B);
    solver->solve();
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+1;

struct Solver_Ioi {
    int n, m, mxd, mxdv, P, V, color[N], last[N];
    long long X;
    vector<int> g1[N], g2[N];

    bool vis[N];
    int par[N], depth[N];

    void init_dfs(int u) {
        vis[u] = true;
        if (depth[u] > mxd) {
            mxd = depth[u];
            mxdv = u;
        }
        for (int v: g1[u]) {
            if (vis[v]) continue;
            g2[u].push_back(v);
            par[v] = u;
            depth[v] = depth[u] + 1;
            init_dfs(v);
        }
    }

    void colorBig(int u) {
        color[u] = depth[u] % 60;
        for (int v: g2[u]) {
            colorBig(v);
        }
    }

    int curr_count;
    int st[N];
    vector<int> ord;

    void prepColorSmall1(int u) {
        color[u] = (curr_count >= 60 ? -1 : curr_count);
        ++curr_count;

        if (color[u] != -1) {
            st[u] = ord.size();
            ord.push_back(u);
        }

        for (int v: g2[u]) {
            prepColorSmall1(v);
            if(color[u] != -1 && ord.back() != u) ord.push_back(u);
        }
    }

    void traverseUp(int v, int offset, set<int> &distinct_mods) { // check both cases where v is in top set and bottom set
        assert(v == last[v]);
        int idx = st[v];
        while(distinct_mods.size() < 60 - offset) {
            long long tmp = Move(ord[idx]);
            assert(color[ord[idx]] != -1);
            X |= tmp << color[ord[idx]];
            distinct_mods.insert(color[ord[idx]]);
            idx = (idx + 1) % ord.size();
        }
        // is this inclusive or exclusive?
        // this function assumes that v has not been visited yet
    }

    void solve() {
        par[0] = -1;
        fill(color, color + N, -1);
        fill(last, last + N, -1);
        init_dfs(0);

        if (mxd >= 59) {
            set<int> distinct_mods;
            colorBig(0);
            distinct_mods.insert(color[P]);
            X |= 1ll * V << color[P];
            for(int v = par[P]; v >= 0 && distinct_mods.size() < 60; v = par[v]) {
                long long tmp = Move(v);
                distinct_mods.insert(color[v]);
                X |= tmp << color[v];
            }
            vector<int> ord;
            for(int v = mxdv; v > 0; v = par[v]) ord.push_back(v);
            reverse(ord.begin(), ord.end());
            for(int v: ord) {
                if(distinct_mods.size() >= 60) break;
                long long tmp = Move(v);
                distinct_mods.insert(color[v]);
                X |= tmp << color[v];
            }
            return;
        }

        prepColorSmall1(0);
        ord.pop_back();
//        for(int x: ord) cerr << x << ' ';
//        cerr << endl;

        for (int i = 0; i < n; i++) {
            last[i] = i;
            while (color[last[i]] == -1) last[i] = par[last[i]];
        }

        for(int i = 0; i < n; i++) {
            if(color[i] != -1) continue;

            int idx = st[last[i]];
            int depth_diff = depth[i] - depth[last[i]];

            set<int> distinct_mods;
            while(distinct_mods.size() < 60 - depth_diff) {
                distinct_mods.insert(color[ord[idx]]);
                idx = (idx + 1) % ord.size();
            }

            for(int mod = 0; mod < 60; mod++) {
                if(!distinct_mods.count(mod)) {
                    color[i] = mod;
                    break;
                }
            }
            assert(ord[st[last[i]]] == last[i]);

//            cerr << i << ' ' << last[i] << ' ' << color[i] << endl;
        }

        set<int> distinct_mods;
        distinct_mods.insert(color[P]);
        X |= 1ll * V << color[P];

        if(last[P] == P) {
            int nxt = ord[(st[P] + 1) % ord.size()];
            assert(last[nxt] == nxt);
            traverseUp(nxt, 0, distinct_mods);
        } else {
            int v;
            for(v = par[P]; last[v] != v; v = par[v]) {
                long long tmp = Move(v);
                distinct_mods.insert(color[v]);
                X |= tmp << color[v];
            }
//            traverseUp(v, depth[v] - depth[last[v]], distinct_mods);
            traverseUp(v, 0, distinct_mods);
        }

    }

    Solver_Ioi(int n, int m, int P, int V, int A[], int B[]) : n(n), m(m), P(P), V(V) {
        for (int i = 0; i < m; i++) {
            g1[A[i]].push_back(B[i]);
            g1[B[i]].push_back(A[i]);
        }
    }
};

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    Solver_Ioi *solverIoi = new Solver_Ioi(n, m, P, V, A, B);
    solverIoi->solve();
    return solverIoi->X;
}

Compilation message (stderr)

Joi.cpp: In member function 'void Solver_Joi::solve()':
Joi.cpp:85:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(distinct_mods.size() < 60 - depth_diff) {
                   ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Ioi.cpp: In member function 'void Solver_Ioi::traverseUp(int, int, std::set<int>&)':
Ioi.cpp:58:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(distinct_mods.size() < 60 - offset) {
               ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
Ioi.cpp: In member function 'void Solver_Ioi::solve()':
Ioi.cpp:114:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(distinct_mods.size() < 60 - depth_diff) {
                   ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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