oj.uz

Submission #1105458

# Submission time Handle Problem Language Result Execution time Memory
1105458 2024-10-26T12:57:08 Z jerzyk Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 642 ms 1728 KB 
#include <bits/stdc++.h>
#include "sphinx.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 250 + 7;
int fau[N], ansclr[N];
vector<int> ed[N], ed2[N];
bool vis[N];
vector<int> dfst, vset[2];

int Find(int v)
{
    if(fau[v] == v) return v;
    return (fau[v] = Find(fau[v]));
}

void Union(int a, int b)
{
    //cout << "Union " << a << " " << b << "\n";
    a = Find(a); b = Find(b);
    fau[max(a, b)] = min(a, b);
}

void DFSN2(int v)
{
    vis[v] = true;
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(Find(v) != Find(ed[v][i]))
            ed2[Find(v)].pb(Find(ed[v][i]));
        if(vis[ed[v][i]])
            continue;
        DFSN2(ed[v][i]);
    }
}

void DFSclr(int v, int c)
{
    vis[v] = true;
    vset[c].pb(v);
    for(int i = 0; i < (int)ed2[v].size(); ++i)
        if(!vis[ed2[v][i]])
            DFSclr(ed2[v][i], c ^ 1);
}

void DoNew(int n)
{
    DFSN2(0);
    for(int i = 0; i < n; ++i) vis[i] = false;
    for(int i = 0; i < n; ++i)
    {
        vector<int> nw;
        sort(ed2[i].begin(), ed2[i].end());
        for(int j = 0; j < (int)ed2[i].size(); ++j)
            if(j == 0 || ed2[i][j] != ed2[i][j - 1])
                nw.pb(ed2[i][j]);
        ed2[i] = nw;
    }
    DFSclr(0, 0);
    for(int i = 0; i < n; ++i) vis[i] = false;
}

void DFS(int v)
{
    vis[v] = true;
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if((!vis[ed[v][i]]) && dfst[ed[v][i]] == dfst[v])
            DFS(ed[v][i]);
}

int Sus(vector<int> que)
{
    int ans = 0, n = que.size();
    dfst.clear();
    for(int i = 0; i < n; ++i)
        if(que[i] != -1)
            dfst.pb(que[i]);
        else
            dfst.pb(-Find(i) - 1);
    for(int i = 0; i < n; ++i)
        if(!vis[i])
        {
            ++ans;
            DFS(i);
        }
    for(int i = 0; i < n; ++i) vis[i] = false;
    return ans;
}

void D1(int n)
{
    vector<int> bas(n, -1), que;
    for(int i = 0; i < n; ++i)
    {
        que = bas;
        que[1] = i;
        if(perform_experiment(que) == 1)
            ansclr[0] = i;
    }
}

void FindClr(int n)
{
    vector<int> bas(n, -1), cur, que;
    cur = vset[1];
    //cerr << "beg " << vset[1].size() << "\n";
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < (int)vset[0].size(); ++j)
            bas[vset[0][j]] = i;
        for(int j = 0; j < (int)vset[1].size(); ++j)
            bas[vset[1][j]] = -1;
        for(int j = 0; j < n; ++j) bas[j] = bas[Find(j)];
        que = bas;
        //for(int j = 0; j < n; ++j)
            //cout << que[j] << " ";
        //cout << "\n";
        int ant = Sus(que);
        int akt = perform_experiment(que);
        int il = ant - akt;
        //cerr << "Clr: " << i << " " << ant << " " << akt << "\n";
        while(il > 0)
        {
            int p = 0, s, k = (int)cur.size() - 1;
            while(p < k)
            {
                s = (p + k) / 2;
                que = bas;
                for(int j = s + 1; j < (int)cur.size(); ++j)
                    que[cur[j]] = n;
                for(int j = 0; j < n; ++j) que[j] = que[Find(j)];
                int abc = Sus(que);
                if(perform_experiment(que) < abc)
                    k = s;
                else
                    p = s + 1;
            }
            //if(cur.size() == 0) return;
            //cerr << "F: " << cur[p] << " " << il << "\n";
            que = bas;
            //for(int j = 0; j < n; ++j)
                //cerr << que[j] << " ";
            //cout << "\n";
            int xd = Sus(que);
            que[cur[p]] = i;
            for(int j = 0; j < n; ++j) que[j] = que[Find(j)];
            /*for(int j = 0; j < n; ++j)
                cerr << que[j] << " ";
            cerr << "\n";*/
            int xd2 = Sus(que);
            //cerr << xd << " " << xd2 << "\n";
            il -= (xd - xd2);
            ansclr[cur[p]] = i;
            bas[cur[p]] = i;
            for(int j = 0; j < n; ++j) bas[j] = bas[Find(j)];
            vector<int> nw;
            for(int j = 0; j < (int)cur.size(); ++j)
                if(j != p)
                nw.pb(cur[j]);
            cur = nw;
        }
    }
}

void FN(int v, int il, int n)
{
    vector<int> cur, bas(n, n), que, ss;
    
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if(!vis[Find(ed[v][i])] && ed[v][i] < v)
        {
            cur.pb(Find(ed[v][i]));
            vis[cur.back()] = true;
        }
    for(int i = 0; i < (int)cur.size(); ++i)
        vis[cur[i]] = false;
    while(il--)
    {
        int p = 0, s, k = cur.size() - 1;
        while(p < k)
        {
            s = (p + k) / 2;
            que = bas;
            for(int i = 0; i <= s; ++i)
                que[cur[i]] = -1;
            que[v] = -1;
            for(int i = 0; i < n; ++i) que[i] = que[Find(i)];
            int ans = perform_experiment(que);
            int ant = Sus(que);
            if(ans < ant)
                k = s;
            else
                p = s + 1;
        }
        ss.pb(cur[p]);
        vector<int> nw;
        for(int i = p + 1; i < (int)cur.size(); ++i) nw.pb(cur[i]);
        cur = nw;
    }
    for(int i = 0; i < (int)ss.size(); ++i)
        Union(v, ss[i]);
}

vector<int> find_colours(int _N, vector<int> _X, vector<int> _Y)
{
    int n = _N;
    vector<int> answer;
    for(int i = 0; i < (int)_X.size(); ++i)
    {
        ed[_X[i]].pb(_Y[i]);
        ed[_Y[i]].pb(_X[i]);
    }
    vector<int> cq(n, n);
    for(int i = 0; i < n; ++i)
        fau[i] = i;

    cq[0] = -1;
    for(int i = 1; i < n; ++i)
    {
        cq[i] = -1;
        int akt = perform_experiment(cq);
        int ant = Sus(cq);
        //cerr << "F:\n";
        //for(int j = 0; j < n; ++j)
            //cerr << Find(j) << " ";
        //cout << "\n";
        //cerr << "Sp: " << i << " " << akt << " " << ant << "\n";
        FN(i, ant - akt, n);
    }
    DoNew(n);
    if((int)vset[1].size() == 0)
        D1(n);
    else
    {
        FindClr(n);
        swap(vset[1], vset[0]);
        FindClr(n);
    }

    for(int i = 0; i < n; ++i)
        answer.pb(ansclr[Find(i)]);
    return answer;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 13

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 3
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 13
2 Correct 1 ms 336 KB #experiments: 3
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 5
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 2 ms 336 KB #experiments: 99
7 Correct 3 ms 336 KB #experiments: 147
8 Correct 2 ms 336 KB #experiments: 153
9 Correct 2 ms 336 KB #experiments: 152
10 Correct 2 ms 336 KB #experiments: 161
11 Correct 2 ms 336 KB #experiments: 178
12 Correct 4 ms 336 KB #experiments: 314
13 Correct 3 ms 336 KB #experiments: 315
14 Correct 2 ms 336 KB #experiments: 99
15 Correct 5 ms 336 KB #experiments: 249
16 Correct 5 ms 592 KB #experiments: 264
17 Correct 4 ms 336 KB #experiments: 285
18 Correct 5 ms 336 KB #experiments: 310
19 Correct 5 ms 496 KB #experiments: 311
20 Correct 6 ms 336 KB #experiments: 327
21 Correct 5 ms 336 KB #experiments: 318
22 Correct 4 ms 336 KB #experiments: 313
23 Correct 4 ms 336 KB #experiments: 316
24 Correct 4 ms 336 KB #experiments: 304
25 Correct 5 ms 336 KB #experiments: 315
26 Correct 4 ms 336 KB #experiments: 280
27 Correct 3 ms 336 KB #experiments: 292
28 Correct 4 ms 452 KB #experiments: 319
29 Correct 4 ms 504 KB #experiments: 265
30 Correct 4 ms 336 KB #experiments: 302
31 Correct 5 ms 336 KB #experiments: 281
32 Correct 5 ms 508 KB #experiments: 315
33 Correct 2 ms 336 KB #experiments: 103
34 Correct 5 ms 336 KB #experiments: 327

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 3
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 2 ms 336 KB #experiments: 99
6 Correct 3 ms 336 KB #experiments: 147
7 Correct 2 ms 336 KB #experiments: 153
8 Correct 2 ms 336 KB #experiments: 152
9 Correct 2 ms 336 KB #experiments: 161
10 Correct 2 ms 336 KB #experiments: 178
11 Correct 4 ms 336 KB #experiments: 314
12 Correct 3 ms 336 KB #experiments: 315
13 Correct 16 ms 336 KB #experiments: 749
14 Correct 22 ms 480 KB #experiments: 751
15 Correct 26 ms 592 KB #experiments: 763
16 Correct 24 ms 480 KB #experiments: 777
17 Correct 21 ms 336 KB #experiments: 907
18 Correct 27 ms 336 KB #experiments: 1176
19 Correct 43 ms 480 KB #experiments: 1813
20 Correct 11 ms 336 KB #experiments: 499
21 Correct 57 ms 480 KB #experiments: 2152

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 3
2 Correct 1 ms 336 KB #experiments: 5
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 3
5 Correct 2 ms 336 KB #experiments: 99
6 Correct 5 ms 336 KB #experiments: 249
7 Correct 5 ms 592 KB #experiments: 264
8 Correct 4 ms 336 KB #experiments: 285
9 Correct 5 ms 336 KB #experiments: 310
10 Correct 5 ms 496 KB #experiments: 311
11 Correct 6 ms 336 KB #experiments: 327
12 Correct 5 ms 336 KB #experiments: 318
13 Correct 108 ms 1352 KB #experiments: 997
14 Correct 143 ms 1608 KB #experiments: 1392
15 Correct 191 ms 1588 KB #experiments: 1679
16 Correct 191 ms 1608 KB #experiments: 1875
17 Correct 233 ms 1728 KB #experiments: 2085
18 Correct 259 ms 1552 KB #experiments: 2138
19 Correct 284 ms 1608 KB #experiments: 2184
20 Correct 36 ms 1216 KB #experiments: 499
21 Correct 256 ms 1492 KB #experiments: 2152

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 13
2 Correct 1 ms 336 KB #experiments: 3
3 Correct 1 ms 336 KB #experiments: 5
4 Correct 1 ms 336 KB #experiments: 5
5 Correct 1 ms 336 KB #experiments: 3
6 Correct 2 ms 336 KB #experiments: 99
7 Correct 3 ms 336 KB #experiments: 147
8 Correct 2 ms 336 KB #experiments: 153
9 Correct 2 ms 336 KB #experiments: 152
10 Correct 2 ms 336 KB #experiments: 161
11 Correct 2 ms 336 KB #experiments: 178
12 Correct 4 ms 336 KB #experiments: 314
13 Correct 3 ms 336 KB #experiments: 315
14 Correct 2 ms 336 KB #experiments: 99
15 Correct 5 ms 336 KB #experiments: 249
16 Correct 5 ms 592 KB #experiments: 264
17 Correct 4 ms 336 KB #experiments: 285
18 Correct 5 ms 336 KB #experiments: 310
19 Correct 5 ms 496 KB #experiments: 311
20 Correct 6 ms 336 KB #experiments: 327
21 Correct 5 ms 336 KB #experiments: 318
22 Correct 4 ms 336 KB #experiments: 313
23 Correct 4 ms 336 KB #experiments: 316
24 Correct 4 ms 336 KB #experiments: 304
25 Correct 5 ms 336 KB #experiments: 315
26 Correct 4 ms 336 KB #experiments: 280
27 Correct 3 ms 336 KB #experiments: 292
28 Correct 4 ms 452 KB #experiments: 319
29 Correct 4 ms 504 KB #experiments: 265
30 Correct 4 ms 336 KB #experiments: 302
31 Correct 5 ms 336 KB #experiments: 281
32 Correct 5 ms 508 KB #experiments: 315
33 Correct 2 ms 336 KB #experiments: 103
34 Correct 5 ms 336 KB #experiments: 327
35 Correct 16 ms 336 KB #experiments: 749
36 Correct 22 ms 480 KB #experiments: 751
37 Correct 26 ms 592 KB #experiments: 763
38 Correct 24 ms 480 KB #experiments: 777
39 Correct 21 ms 336 KB #experiments: 907
40 Correct 27 ms 336 KB #experiments: 1176
41 Correct 43 ms 480 KB #experiments: 1813
42 Correct 11 ms 336 KB #experiments: 499
43 Correct 57 ms 480 KB #experiments: 2152
44 Correct 108 ms 1352 KB #experiments: 997
45 Correct 143 ms 1608 KB #experiments: 1392
46 Correct 191 ms 1588 KB #experiments: 1679
47 Correct 191 ms 1608 KB #experiments: 1875
48 Correct 233 ms 1728 KB #experiments: 2085
49 Correct 259 ms 1552 KB #experiments: 2138
50 Correct 284 ms 1608 KB #experiments: 2184
51 Correct 36 ms 1216 KB #experiments: 499
52 Correct 256 ms 1492 KB #experiments: 2152
53 Correct 64 ms 336 KB #experiments: 1731
54 Correct 53 ms 572 KB #experiments: 1706
55 Correct 60 ms 584 KB #experiments: 1660
56 Correct 62 ms 572 KB #experiments: 1586
57 Correct 291 ms 808 KB #experiments: 2160
58 Correct 209 ms 932 KB #experiments: 2051
59 Correct 222 ms 928 KB #experiments: 2054
60 Correct 236 ms 816 KB #experiments: 2153
61 Correct 44 ms 336 KB #experiments: 1907
62 Correct 47 ms 336 KB #experiments: 2090
63 Correct 67 ms 584 KB #experiments: 2146
64 Correct 68 ms 544 KB #experiments: 1592
65 Correct 67 ms 540 KB #experiments: 1570
66 Correct 67 ms 556 KB #experiments: 1661
67 Correct 68 ms 560 KB #experiments: 1690
68 Correct 60 ms 576 KB #experiments: 1582
69 Correct 66 ms 572 KB #experiments: 1619
70 Correct 71 ms 572 KB #experiments: 1697
71 Correct 73 ms 576 KB #experiments: 1540
72 Correct 62 ms 516 KB #experiments: 1823
73 Correct 59 ms 516 KB #experiments: 1590
74 Correct 70 ms 536 KB #experiments: 1777
75 Correct 65 ms 552 KB #experiments: 1550
76 Correct 63 ms 584 KB #experiments: 1665
77 Correct 63 ms 572 KB #experiments: 1561
78 Correct 80 ms 760 KB #experiments: 1668
79 Correct 80 ms 600 KB #experiments: 1551
80 Correct 80 ms 596 KB #experiments: 1649
81 Correct 86 ms 608 KB #experiments: 1664
82 Correct 110 ms 632 KB #experiments: 2093
83 Correct 327 ms 1364 KB #experiments: 1776
84 Correct 642 ms 1440 KB #experiments: 2136
85 Correct 20 ms 592 KB #experiments: 500
86 Correct 150 ms 756 KB #experiments: 2151