Submission #418808

#	Time	Username	Problem	Language	Result	Execution time	Memory
418808		Osama_Alkhodairy	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	26 ms	4108 KiB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
#define ll long long

const int NA = 10001;
const int KA = 60;

int mxA[NA], pA[NA], tA[NA], dfstimeA;
vector <int> vA[NA];

int findA(int x){
    if(pA[x] == x) return x;
    return pA[x] = findA(pA[x]);
}
bool mergeA(int x, int y){
    x = findA(x);
    y = findA(y);
    if(x == y) return 0;
    pA[x] = y;
    return 1;
}
void dfszA(int node, int pnode){
    for(auto &i : vA[node]){
        if(i == pnode) continue;
        dfszA(i, node);
        mxA[node] = max(mxA[node], mxA[i] + 1);
    }
}
void dfsA(int node, int pnode){
    tA[node] = dfstimeA++;
    for(auto &i : vA[node]){
        if(i == pnode) continue;
        dfsA(i, node);
    }
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
    for(int i = 0 ; i < N ; i++){
        pA[i] = i;
    }
    for(int i = 0 ; i < M ; i++){
        if(mergeA(A[i], B[i])){
            vA[A[i]].push_back(B[i]);
            vA[B[i]].push_back(A[i]);
        }
    }
    dfszA(0, 0);
    for(int i = 0 ; i < N ; i++){
        sort(vA[i].begin(), vA[i].end(), [&](int l, int r){
            return mxA[l] > mxA[r];
        });
    }
    dfsA(0, 0);
    for(int i = 0 ; i < N ; i++){
        MessageBoard(i, (X >> (tA[i] % KA)) & 1);
    }
}

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define ll long long

const int NB = 10001;
const int KB = 60;

int mxB[NB], pB[NB], tB[NB], szB[NB], XB[KB], unknownB = KB, dfstimeB;
vector <int> vB[NB];

void updateB(int bit, int v){
    if(XB[bit] == -1){
        unknownB--;
        XB[bit] = v;
    }
}
int findB(int x){
    if(pB[x] == x) return x;
    return pB[x] = findB(pB[x]);
}
bool mergeB(int x, int y){
    x = findB(x);
    y = findB(y);
    if(x == y) return 0;
    pB[x] = y;
    return 1;
}
void dfszB(int node, int pnode){
    for(auto &i : vB[node]){
        if(i == pnode) continue;
        dfszB(i, node);
        mxB[node] = max(mxB[node], mxB[i] + 1);
    }
}
void dfsB(int node, int pnode){
    szB[node] = 1;
    tB[node] = dfstimeB++;
    for(auto &i : vB[node]){
        if(i == pnode) continue;
        pB[i] = node;
        dfsB(i, node);
        szB[node] += szB[i];
    }
}
void my_moveB(int dest){
    int v = Move(dest);
    assert(0 <= v && v <= 1);
    updateB(tB[dest] % KB, v);
}
void solveB(int node, int k){
    if(unknownB == 0) return;
    k--;
    vector <int> all;
    for(auto &i : vB[node]){
        if(unknownB == 0) return;
        if(k == 0) break;
        if(k < szB[i]){
            my_moveB(i);
            solveB(i, k);
            break;
        }
        else{
            all.push_back(i);
            k -= szB[i];
        }
    }
    reverse(all.begin(), all.end());
    for(auto &i : all){
        if(unknownB == 0) return;
        my_moveB(i);
        solveB(i, szB[i]);
    }
    if(unknownB == 0) return;
    if(pB[node] != -1) my_moveB(pB[node]);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    for(int i = 0 ; i < KB ; i++){
        XB[i] = -1;
    }
    for(int i = 0 ; i < N ; i++){
        pB[i] = i;
    }
    for(int i = 0 ; i < M ; i++){
        if(mergeB(A[i], B[i])){
            vB[A[i]].push_back(B[i]);
            vB[B[i]].push_back(A[i]);
        }
    }
    dfszB(0, 0);
    for(int i = 0 ; i < N ; i++){
        sort(vB[i].begin(), vB[i].end(), [&](int l, int r){
            return mxB[l] > mxB[r];
        });
    }
    pB[0] = -1;
    dfsB(0, 0);
    for(int i = 1 ; i < N ; i++){
        vB[i].erase(find(vB[i].begin(), vB[i].end(), pB[i]));
    }
    int node = P;
    int v = V;
    updateB(tB[node] % KB, v);
    while(szB[node] < KB){
        my_moveB(pB[node]);
        node = pB[node];
    }
    solveB(node, KB);
    ll X = 0;
    for(int i = KB - 1 ; i >= 0 ; i--){
        X = 2 * X + XB[i];
    }
    return X;
}

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