oj.uz

답안 #948231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948231 2024-03-18T00:08:23 Z Nhoksocqt1 가장 긴 여행 (IOI23_longesttrip) C++17
100 / 100
 15 ms 1232 KB 
#ifndef Nhoksocqt1
    #include "longesttrip.h"
#endif // Nhoksocqt1
#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;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(41287);
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 260;

#ifdef Nhoksocqt1

bitset<MAXN> adjp[MAXN], idA, idB, bsA, bsB;
struct Jury {
    int n, d;

    void init(int _n, int _d) {
        n = _n, d = _d;
        int u, v;
        bool check(0);
        while(cin >> u >> v) {
            adjp[u][v] = adjp[v][u] = 1;
            check = 1;
        }

        if(!check) {
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    for (int k = j + 1; k < n; ++k) {
                        int cnt = adjp[i][j] + adjp[i][k] + adjp[j][k];
                        if(cnt < d) {
                            vector<ii> p;
                            p.push_back(ii(i, j));
                            p.push_back(ii(i, k));
                            p.push_back(ii(j, k));

                            while(cnt < d) {
                                int r = Random(0, 2);
                                if(adjp[p[r].fi][p[r].se])
                                    continue;

                                ++cnt;
                                adjp[p[r].fi][p[r].se] = adjp[p[r].se][p[r].fi] = 1;
                                cout << p[r].fi << ' ' << p[r].se << '\n';
                            }
                        }
                    }
                }
            }
        }
    }

    bool are_connected(const vector<int> &A, const vector<int> &B) {
        bsA = bsB = idA = idB = 0;
        for (int it = 0; it < sz(A); ++it) {
            bsA |= adjp[A[it]];
            idA[A[it]] = 1;
        }

        for (int it = 0; it < sz(B); ++it) {
            bsB |= adjp[B[it]];
            idB[B[it]] = 1;
        }

        return ((bsA & idB).count() > 0 || (bsB & idA).count() > 0);
    }

} jury;

#endif // Nhoksocqt1

vector<int> A[MAXN];
int nxt[MAXN], numNode;
bool adj[MAXN][MAXN], dx[MAXN];

int cntAsk(0);
bool check_are_connected(vector<int> A, vector<int> B) {
    ++cntAsk;
    #ifdef Nhoksocqt1
        return jury.are_connected(A, B);
    #else
        return are_connected(A, B);
    #endif // Nhoksocqt1
}

void mergeLine(deque<int> &line1, deque<int> &line2, bool mergeBack1, bool mergeBack2) {
    if(mergeBack1 && mergeBack2) {
        while(sz(line2)) {
            line1.push_back(line2.back());
            line2.pop_back();
        }

        return;
    }

    if(!mergeBack1 && !mergeBack2) {
        while(sz(line2)) {
            line1.push_front(line2.front());
            line2.pop_front();
        }

        return;
    }

    if(!mergeBack1)
        swap(line1, line2);

    while(sz(line2)) {
        line1.push_back(line2.front());
        line2.pop_front();
    }
}

void mergeLine(deque<int> &line1, deque<int> &line2) {
    if(sz(line2) == 0)
        return;

    if(check_are_connected({line1.back()}, {line2.back()})) {
        mergeLine(line1, line2, 1, 1);
        return;
    }

    if(check_are_connected({line1.back()}, {line2.front()})) {
        mergeLine(line1, line2, 1, 0);
        return;
    }

    if(check_are_connected({line1.front()}, {line2.back()})) {
        mergeLine(line1, line2, 0, 1);
        return;
    }

    if(check_are_connected({line1.front()}, {line2.front()})) {
        mergeLine(line1, line2, 0, 0);
        return;
    }

    vector<int> l1, l2;
    while(sz(line1)) {
        l1.push_back(line1.front());
        line1.pop_front();
    }

    while(sz(line2)) {
        l2.push_back(line2.front());
        line2.pop_front();
    }

    if(!check_are_connected(l1, l2)) {
        for (int it = sz(l1) - 1; it >= 0; --it)
            line1.push_back(l1[it]);

        return;
    }

    int l(0), r(sz(l1) - 1), pos1(-1), pos2(-1);
    while(l <= r) {
        vector<int> p;
        int mid = (l + r) >> 1;
        for (int it = 0; it <= mid; ++it)
            p.push_back(l1[it]);

        if(check_are_connected(p, l2)) {
            pos1 = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    l = 0, r = sz(l2) - 1;
    while(l <= r) {
        vector<int> p;
        int mid = (l + r) >> 1;
        for (int it = 0; it <= mid; ++it)
            p.push_back(l2[it]);

        if(check_are_connected({l1[pos1]}, p)) {
            pos2 = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    vector<int> p;
    for (int i = pos1 - 1; i >= 0; --i)
        p.push_back(l1[i]);

    for (int i = sz(l1) - 1; i >= pos1; --i)
        p.push_back(l1[i]);

    for (int i = pos2; i >= 0; --i)
        p.push_back(l2[i]);

    for (int i = sz(l2) - 1; i > pos2; --i)
        p.push_back(l2[i]);

    while(sz(line1))
        line1.pop_back();

    for (int it = sz(p) - 1; it >= 0; --it)
        line1.push_back(p[it]);
}

vector<int> longest_trip(int N, int D) {
    numNode = N;
    if(D == 3) {
        vector<int> ans;
        for (int i = 0; i < numNode; ++i)
            ans.push_back(i);

        return ans;
    }

    vector<int> ans, id;
    for (int i = 0; i < numNode; ++i)
        id.push_back(i);

    shuffle(id.begin(), id.end(), rng);

    deque<int> line1, line2;
    line1.push_back(id[0]);
    line2.push_back(id[1]);

    bool needAsk(1);
    for (int i = 2; i < numNode; ++i) {
        if(check_are_connected({line1.back()}, {id[i]})) {
            line1.push_back(id[i]);
            needAsk = 1;
        } else
            if(!needAsk || check_are_connected({line2.back()}, {id[i]})) {
                line2.push_back(id[i]);
                needAsk = 0;
            } else {
                if(i + 2 < numNode) {
                    bool c1 = check_are_connected({id[i]}, {id[i + 1]});
                    bool c2 = check_are_connected({id[i]}, {id[i + 2]});

                    if(c1 && c2) {
                        mergeLine(line1, line2, 1, 1);
                        line2.push_back(id[i + 1]);
                        line2.push_back(id[i]);
                        line2.push_back(id[i + 2]);
                    } else
                        if(!c1 && !c2) {
                            line1.push_back(id[i + 1]);
                            line1.push_back(id[i + 2]);
                            mergeLine(line1, line2, 1, 1);
                            line2.push_back(id[i]);
                        } else {
                            if(!c1) {
                                line1.push_back(id[i + 1]);
                            } else {
                                line1.push_back(id[i + 2]);
                            }

                            mergeLine(line1, line2, 1, 1);
                            if(!c1) {
                                line2.push_back(id[i + 2]);
                            } else {
                                line2.push_back(id[i + 1]);
                            }

                            line2.push_back(id[i]);
                        }

                    i += 2;
                } else {
                    mergeLine(line1, line2, 1, 1);
                    line2.push_back(id[i]);
                }

                needAsk = 1;
            }
    }

    if(sz(line1) < sz(line2))
        swap(line1, line2);

    mergeLine(line1, line2);

    ans.clear();
    while(sz(line1)) {
        ans.push_back(line1.front());
        line1.pop_front();
    }

    return ans;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "longesttrip"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int n, d;
    cin >> n >> d;
    jury.init(n, d);

    vector<int> path = longest_trip(n, d);
    cout << "CNT ASK: " << cntAsk << '\n';
    cout << "ANSWER " << sz(path) << ": ";
    for (int it = 0; it < sz(path); ++it)
        cout << path[it] << ' '; cout << '\n';

    return 0;
}

#endif // Nhoksocqt1

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 352 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 356 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 356 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 356 KB Output is correct
2 Correct 6 ms 356 KB Output is correct
3 Correct 5 ms 356 KB Output is correct
4 Correct 5 ms 356 KB Output is correct
5 Correct 4 ms 608 KB Output is correct
6 Correct 9 ms 352 KB Output is correct
7 Correct 6 ms 356 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 4 ms 356 KB Output is correct
10 Correct 4 ms 356 KB Output is correct
11 Correct 5 ms 352 KB Output is correct
12 Correct 4 ms 356 KB Output is correct
13 Correct 4 ms 356 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 356 KB Output is correct
2 Correct 5 ms 356 KB Output is correct
3 Correct 4 ms 356 KB Output is correct
4 Correct 4 ms 356 KB Output is correct
5 Correct 5 ms 356 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 6 ms 344 KB Output is correct
14 Correct 15 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Correct 6 ms 344 KB Output is correct
17 Correct 5 ms 600 KB Output is correct
18 Correct 5 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 5 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 6 ms 344 KB Output is correct
24 Correct 5 ms 596 KB Output is correct
25 Correct 13 ms 344 KB Output is correct
26 Correct 12 ms 344 KB Output is correct
27 Correct 9 ms 344 KB Output is correct
28 Correct 8 ms 344 KB Output is correct
29 Correct 9 ms 344 KB Output is correct
30 Correct 6 ms 600 KB Output is correct
31 Correct 8 ms 612 KB Output is correct
32 Correct 7 ms 460 KB Output is correct
33 Correct 5 ms 356 KB Output is correct
34 Correct 5 ms 356 KB Output is correct
35 Correct 7 ms 356 KB Output is correct
36 Correct 4 ms 356 KB Output is correct
37 Correct 5 ms 612 KB Output is correct
38 Correct 6 ms 612 KB Output is correct
39 Correct 6 ms 356 KB Output is correct
40 Correct 6 ms 356 KB Output is correct
41 Correct 6 ms 356 KB Output is correct
42 Correct 6 ms 356 KB Output is correct
43 Correct 6 ms 356 KB Output is correct
44 Correct 6 ms 612 KB Output is correct
45 Correct 8 ms 356 KB Output is correct
46 Correct 10 ms 356 KB Output is correct
47 Correct 6 ms 356 KB Output is correct
48 Correct 6 ms 356 KB Output is correct
49 Correct 6 ms 356 KB Output is correct
50 Correct 5 ms 472 KB Output is correct
51 Correct 7 ms 468 KB Output is correct
52 Correct 7 ms 468 KB Output is correct
53 Correct 7 ms 612 KB Output is correct
54 Correct 6 ms 600 KB Output is correct
55 Correct 6 ms 604 KB Output is correct
56 Correct 6 ms 728 KB Output is correct
57 Correct 6 ms 616 KB Output is correct
58 Correct 6 ms 1232 KB Output is correct
59 Correct 7 ms 864 KB Output is correct
60 Correct 6 ms 468 KB Output is correct
61 Correct 6 ms 860 KB Output is correct
62 Correct 6 ms 604 KB Output is correct
63 Correct 9 ms 720 KB Output is correct
64 Correct 7 ms 472 KB Output is correct

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 8 ms 848 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 13 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Correct 7 ms 600 KB Output is correct
17 Correct 5 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 5 ms 344 KB Output is correct
21 Correct 12 ms 344 KB Output is correct
22 Correct 14 ms 344 KB Output is correct
23 Correct 7 ms 344 KB Output is correct
24 Correct 7 ms 344 KB Output is correct
25 Correct 11 ms 344 KB Output is correct
26 Correct 5 ms 456 KB Output is correct
27 Correct 5 ms 460 KB Output is correct
28 Correct 7 ms 460 KB Output is correct
29 Correct 5 ms 344 KB Output is correct
30 Correct 5 ms 344 KB Output is correct
31 Correct 5 ms 344 KB Output is correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 7 ms 344 KB Output is correct
34 Correct 8 ms 344 KB Output is correct
35 Correct 8 ms 344 KB Output is correct
36 Correct 8 ms 344 KB Output is correct
37 Correct 6 ms 464 KB Output is correct
38 Correct 7 ms 468 KB Output is correct
39 Correct 9 ms 724 KB Output is correct
40 Correct 7 ms 600 KB Output is correct
41 Correct 7 ms 604 KB Output is correct
42 Correct 6 ms 600 KB Output is correct
43 Correct 6 ms 344 KB Output is correct
44 Correct 5 ms 344 KB Output is correct
45 Correct 5 ms 344 KB Output is correct
46 Correct 5 ms 344 KB Output is correct
47 Correct 5 ms 344 KB Output is correct
48 Correct 6 ms 600 KB Output is correct
49 Correct 5 ms 712 KB Output is correct
50 Correct 5 ms 344 KB Output is correct
51 Correct 5 ms 344 KB Output is correct
52 Correct 6 ms 344 KB Output is correct
53 Correct 6 ms 344 KB Output is correct
54 Correct 6 ms 600 KB Output is correct
55 Correct 6 ms 344 KB Output is correct
56 Correct 6 ms 464 KB Output is correct
57 Correct 7 ms 456 KB Output is correct
58 Correct 6 ms 460 KB Output is correct
59 Correct 5 ms 344 KB Output is correct
60 Correct 6 ms 344 KB Output is correct
61 Correct 6 ms 344 KB Output is correct
62 Correct 5 ms 864 KB Output is correct
63 Correct 5 ms 476 KB Output is correct
64 Correct 7 ms 980 KB Output is correct
65 Correct 7 ms 612 KB Output is correct
66 Correct 6 ms 716 KB Output is correct
67 Correct 6 ms 604 KB Output is correct
68 Correct 8 ms 464 KB Output is correct
69 Correct 8 ms 604 KB Output is correct
70 Correct 6 ms 720 KB Output is correct
71 Correct 6 ms 860 KB Output is correct
72 Correct 6 ms 976 KB Output is correct
73 Correct 6 ms 608 KB Output is correct
74 Correct 6 ms 724 KB Output is correct
75 Correct 7 ms 976 KB Output is correct
76 Correct 7 ms 608 KB Output is correct
77 Correct 6 ms 732 KB Output is correct
78 Correct 8 ms 472 KB Output is correct
79 Correct 6 ms 720 KB Output is correct
80 Correct 6 ms 1120 KB Output is correct
81 Correct 7 ms 864 KB Output is correct
82 Correct 7 ms 864 KB Output is correct