oj.uz

답안 #107400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107400 2019-04-24T03:26:02 Z szawinis Amusement Park (JOI17_amusement_park) C++17
0 / 100
 122 ms 5896 KB 
#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.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();
}

#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) { // check both cases where v is in top set and bottom set
        assert(v == last[v]);
        set<int> distinct_mods;
        int idx = st[v];
        while(distinct_mods.size() < 60 - offset) {
            long long tmp = Move(ord[idx]);
            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) {
            colorBig(0);
            X |= 1ll * V << color[P];
            for(int v = par[P]; v >= 0; v = par[v]) {
                long long tmp = Move(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) {
                long long tmp = Move(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;
        }

        X |= 1ll * V << P;

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

    }

    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

Joi.cpp: In member function 'void Solver_Joi::solve()':
Joi.cpp:84: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)':
Ioi.cpp:59: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:109:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(distinct_mods.size() < 60 - depth_diff) {
                   ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2064 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 5840 KB Output is correct
2 Correct 32 ms 5780 KB Output is correct
3 Correct 35 ms 5896 KB Output is correct
4 Incorrect 122 ms 4240 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1928 KB Output is correct
2 Correct 6 ms 1932 KB Output is correct
3 Correct 5 ms 1920 KB Output is correct
4 Incorrect 8 ms 2516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 5764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 5720 KB Output isn't correct
2 Halted 0 ms 0 KB -