답안 #856501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856501	2023-10-03T17:53:44 Z	Nhoksocqt1	CEOI16_icc (CEOI16_icc)	C++17	100 / 100	76 ms	856 KB

icc

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
 
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
 
template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}
 
const int MAXN = 102;
 
vector<int> adj[MAXN], B[MAXN];
int a[MAXN], b[MAXN], lt[MAXN], numNode;
bool answer[MAXN];
 
void dfs(int u) {
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(lt[v] < 0) {
            lt[v] = lt[u];
            dfs(v);
        }
    }
}
 
#ifdef Nhoksocqt1
 
vector<int> jAdj[MAXN];
vector<ii> jury_edges;
int juryLT[MAXN], cntJury(0);
bool jury_hase[MAXN][MAXN];
 
void jury_dfs(int u) {
    for (int it = 0; it < sz(jAdj[u]); ++it) {
        int v(jAdj[u][it]);
        if(!juryLT[v]) {
            juryLT[v] = juryLT[u];
            jury_dfs(v);
        }
    }
}
 
void addRoad(void) {
    if(cntJury >= numNode)
        return;
 
    int u(jury_edges[cntJury].fi), v(jury_edges[cntJury].se);
    jAdj[u].push_back(v);
    jAdj[v].push_back(u);
    jury_hase[u][v] = jury_hase[v][u] = 1;
    for (int i = 1; i <= numNode; ++i)
        juryLT[i] = 0;
 
    int cntNow(0);
    for (int i = 1; i <= numNode; ++i) {
        if(!juryLT[i]) {
            juryLT[i] = ++cntNow;
            jury_dfs(i);
        }
    }
}
 
void setRoad(int u, int v) {
    if(u > v)
        swap(u, v);
 
    assert(u == jury_edges[cntJury].fi && v == jury_edges[cntJury].se);
    ++cntJury;
    addRoad();
}
 
int query(int na, int nb, int a[], int b[]) {
    /*cout << "QUERY FOR :\n" << na << ' ';
    for (int it = 0; it < na; ++it) cout << a[it] << ' '; cout << '\n' << nb << ' ';
    for (int it = 0; it < nb; ++it) cout << b[it] << ' '; cout << '\n';*/
 
    for (int i = 0; i < na; ++i) {
        for (int j = 0; j < nb; ++j) {
            if(jury_hase[min(a[i], b[j])][max(a[i], b[j])])
                return 1;
        }
    }
 
    return 0;
}
 
#endif // Nhoksocqt1
 
void run(int _N) {
    /*int res(0);
    for (int i = 1; i < 100; ++i) {
        int x = 31 - __builtin_clz(i + 1) + (__builtin_popcount(i + 1) > 1);
        res += 2 * x - 1;
 
        int y = 31 - __builtin_clz(i / 2 + 1) + (__builtin_popcount(i / 2 + 1) > 1);
        int z = 31 - __builtin_clz((i + 1) / 2 + 1) + (__builtin_popcount((i + 1) / 2 + 1) > 1);
        res += y + z;
        cout << 2 * x - 1 << ' ' << y << ' ' << z << '\n';
    }
 
    cout << '.' << res << '\n';
    return;*/
 
    numNode = _N;
    for (int i = 1; i < numNode; ++i) {
        for (int j = 0; j <= numNode; ++j)
            lt[j] = -1, B[j].clear();
 
        int cnt(0);
        for (int j = 1; j <= numNode; ++j) {
            if(lt[j] < 0) {
                lt[j] = cnt++;
                dfs(j);
            }
 
            B[lt[j]].push_back(j);
        }
 
        int I(0), J(0), maskd(0), log(0);
        while((1 << log) < cnt)
            ++log;
 
        for (int i = log - 1; i >= 0; --i) {
            int na(0), nb(0);
            for (int j = 0; j < cnt; ++j) {
                for (int it = 0; it < sz(B[j]); ++it) {
                    int u(B[j][it]);
                    if(j >> i & 1) {
                        a[na++] = u;
                    } else {
                        b[nb++] = u;
                    }
                }
            }
 
            answer[i] = query(na, nb, a, b);
            //cout << answer[i] << '\n';
        }
 
        for (int i = log - 1; i >= 0; --i) {
            if(!answer[i])
                continue;
 
            maskd |= (1 << i);
            if(!J) {
                J ^= (1 << i);
                continue;
            }
 
            I ^= (1 << i);
            int na(0), nb(0);
            for (int j = 0; j < cnt; ++j) {
                if((I & maskd) != (j & maskd) && (J & maskd) != (j & maskd))
                    continue;
 
                for (int it = 0; it < sz(B[j]); ++it) {
                    int u(B[j][it]);
                    if((I & maskd) == (j & maskd)) {
                        a[na++] = u;
                    } else {
                        b[nb++] = u;
                    }
                }
            }
 
            int ansNow = (!na || !nb) ? 0 : query(na, nb, a, b);
            if(!ansNow) {
                I ^= (1 << i);
                J ^= (1 << i);
            }
        }
 
        //cout << I << ' ' << J << '\n';
        for (int i = log - 1; i >= 0; --i) {
            if(answer[i])
                continue;
 
            maskd |= (1 << i);
            int na(0), nb(0);
            for (int j = 0; j < cnt; ++j) {
                if((I & maskd) != (j & maskd) && (J & maskd) != (j & maskd))
                    continue;
 
                for (int it = 0; it < sz(B[j]); ++it) {
                    int u(B[j][it]);
                    if((I & maskd) == (j & maskd)) {
                        a[na++] = u;
                    } else {
                        b[nb++] = u;
                    }
                }
            }
 
            int ansNow = (!na || !nb) ? 0 : query(na, nb, a, b);
            if(!ansNow) {
                I ^= (1 << i);
                J ^= (1 << i);
            }
        }
 
        int na(0), nb(0), K(0), L(0);
        for (int it = 0; it < sz(B[J]); ++it)
            b[nb++] = B[J][it];
 
        log = 0;
        while((1 << log) < sz(B[I]))
            ++log;
 
        maskd = 0;
        for (int j = 0; j < log; ++j) {
            na = 0;
            K ^= (1 << j);
            maskd |= (1 << j);
            for (int it = 0; it < sz(B[I]); ++it) {
                if((it & maskd) == (K & maskd))
                    a[na++] = B[I][it];
            }
 
            bool ansNow = query(na, nb, a, b);
            if(!ansNow)
                K ^= (1 << j);
        }
 
        log = maskd = 0;
        while((1 << log) < sz(B[J]))
            ++log;
 
        na = 1;
        a[0] = B[I][K];
 
        for (int j = 0; j < log; ++j) {
            nb = 0;
            L ^= (1 << j);
            maskd |= (1 << j);
            for (int it = 0; it < sz(B[J]); ++it) {
                if((it & maskd) == (L & maskd))
                    b[nb++] = B[J][it];
            }
 
            bool ansNow = query(na, nb, a, b);
            if(!ansNow)
                L ^= (1 << j);
        }
 
        //cout << "NEW ROADS: " << B[I][K] << ' ' << B[J][L] << '\n';
        setRoad(B[I][K], B[J][L]);
        adj[B[I][K]].push_back(B[J][L]);
        adj[B[J][L]].push_back(B[I][K]);
    }
}
 

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	600 KB	Ok! 117 queries used.
2	Correct	4 ms	604 KB	Ok! 117 queries used.

Subtask #2

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	600 KB	Ok! 656 queries used.
2	Correct	23 ms	600 KB	Ok! 576 queries used.
3	Correct	23 ms	600 KB	Ok! 619 queries used.

Subtask #3

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	640 KB	Ok! 1613 queries used.
2	Correct	66 ms	600 KB	Ok! 1406 queries used.
3	Correct	75 ms	604 KB	Ok! 1613 queries used.
4	Correct	74 ms	600 KB	Ok! 1593 queries used.

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	600 KB	Ok! 1580 queries used.
2	Correct	74 ms	600 KB	Ok! 1570 queries used.
3	Correct	76 ms	856 KB	Ok! 1608 queries used.
4	Correct	75 ms	648 KB	Ok! 1613 queries used.

Subtask #5

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	600 KB	Ok! 1581 queries used.
2	Correct	72 ms	648 KB	Ok! 1581 queries used.
3	Correct	71 ms	644 KB	Ok! 1533 queries used.
4	Correct	73 ms	628 KB	Ok! 1583 queries used.
5	Correct	75 ms	600 KB	Ok! 1613 queries used.
6	Correct	72 ms	632 KB	Ok! 1529 queries used.

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	644 KB	Ok! 1563 queries used.
2	Correct	73 ms	624 KB	Ok! 1591 queries used.