Submission #991844

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991844	2024-06-03T08:40:10 Z	danikoynov	Airline Route Map (JOI18_airline)	C++14	37 / 100	420 ms	109332 KB

Alice
Bob

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e3 + 10;
const int maxbit = 10;
const int fict = 2;
/**
from 0 to N - 1 : normal vertexes
from N to N + maxbit - 1 : binary powers
from N + maxbit to N + maxbit + fict - 1 : fictitious vertexes
vertex N + maxbit is connected to all except the binary powers

*/
void Alice( int N, int M, int A[], int B[] )
{
    if (N == 1 && M == 0)
    {
        InitG(1, 0);
        return;
    }
    vector < pair < int, int > > edges;
    for (int i = 0; i < M; i ++)
        edges.push_back({A[i], B[i]});
    for (int i = 0; i < N; i ++)
    {
        for (int bit = 0; bit < maxbit; bit ++)
        {
            if ((i & (1 << bit)) > 0)
                edges.push_back({i, N + bit});
        }
    }
    for (int i = 0; i < N + maxbit; i ++)
        edges.push_back({N + maxbit, i});
    for (int i = 0; i < N; i ++)
    {
        edges.push_back({N + maxbit + 1, i});
    }


    for (int i = N + 1; i < N + maxbit; i ++)
        edges.push_back({i - 1, i});

    InitG(N + maxbit + fict, edges.size());
    int cnt = 0;
    for (pair < int, int > cur : edges)
    {
        MakeG(cnt ++, cur.first, cur.second);
    }
}

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e3 + 10;
struct edge
{
    int v, u;

    edge(int _v = 0, int _u = 0)
    {
        v = _v;
        u = _u;
    }
}edges[MAXN * MAXN];

int deg[MAXN], non_bin[MAXN];
vector < int > adj[MAXN];
int value[MAXN], ridx[MAXN];
vector < int > path;
void dfs(int v, int p)
{
    path.push_back(v);
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        dfs(u, v);
    }
}

const int MAXBIT = 10;
const int FICT = 2;

int tf[MAXN];
void Bob( int V, int U, int C[], int D[] )
{
    if (V == 1 && U == 0)
    {
        InitMap(1, 0);
        return;
    }
    for (int i = 0; i < U; i ++)
    {
        edges[i] = edge(C[i], D[i]);
        deg[C[i]] ++;
        deg[D[i]] ++;
        //cout << C[i] << " " << D[i] << endl;

    }
    ///exit(0);

    int mx = 0;
    for (int i = 0; i < V; i ++)
        if (deg[i] > deg[mx])
        mx = i;


    for (int i = 0; i < U; i ++)
    {
        if (C[i] == mx)
            tf[D[i]] = 1;
        else
        if (D[i] == mx)
            tf[C[i]] = 1;
    }

    tf[mx] = 1;
    int fx = 0;
    while(tf[fx] == 1)
        fx ++;


    non_bin[mx] = 1;
    non_bin[fx] = 1;

        for (int i = 0; i < U; i ++)
    {
        if (C[i] == fx)
            non_bin[D[i]] = 1;
        else
        if (D[i] == fx)
            non_bin[C[i]] = 1;
    }



    for (int i = 0; i < U; i ++)
    {
        if (non_bin[C[i]] || non_bin[D[i]] || C[i] == fx || C[i] == mx || D[i] == fx || D[i] == mx)
            continue;

        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }

    int ver = -1;
    for (int i = 0; i < V; i ++)
    {
        ///cout << "non bin " << i << " : " << non_bin[i] << " " << deg[i] << endl;
        if (non_bin[i] == 0 && adj[i].size() == 1)
            ver = i;
    }
    assert(ver != -1);

    ///cout << "ver " << ver << endl;
    dfs(ver, - 1);
    ///reverse(path.begin(), path.end());
    //for (int p : path)
      //  cout << p << " ";
      //  cout << endl;
    for (int i = 0; i < V; i ++)
        adj[i].clear();
    for (int i = 0; i < U; i ++)
    {
                adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }vector < pair < int, int > > ls;
    for (int i = 0; i < path.size(); i ++)
    {
        value[path[i]] = (1 << i);
    }


    int N = V - MAXBIT - FICT;
    for (int i = 0; i < V; i ++)
    {
        for (int u : adj[i])
        {
            if (non_bin[u] == 0)
            ridx[i] += value[u];
        }
    }
    bool sw = false;
    for (int i = 0; i < V; i ++)
    {
        if (non_bin[i] == 0 || i == mx || i == fx)
        continue;
        if (ridx[i] >= N)
            sw = true;
    }

    if (sw)
    {
        reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); i ++)
    {
        value[path[i]] = (1 << i);
    }
    for (int i = 0; i < V; i ++)
        ridx[i] = 0;

    for (int i = 0; i < V; i ++)
    {
        for (int u : adj[i])
        {
            if (non_bin[u] == 0)
            ridx[i] += value[u];
        }
    }
    }


    for (int i = 0; i < U; i ++)
    {
        if (C[i] == mx || D[i] == mx)
            continue;
            if (C[i] == fx || D[i] == fx)
            continue;
        if (non_bin[C[i]] == 0 || non_bin[D[i]] == 0)
            continue;
        ls.push_back({ridx[C[i]], ridx[D[i]]});
        ///cout << "edge " << ls.back().first << " " << ls.back().second << endl;

    }

    InitMap(V - FICT - MAXBIT, ls.size());
    for (pair < int, int > cur : ls)
        MakeMap(cur.first, cur.second);




}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < path.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
Bob.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 | for (int i = 0; i < path.size(); i ++)
      |                 ~~^~~~~~~~~~~~~
Bob.cpp:169:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  169 |         if (C[i] == mx || D[i] == mx)
      |         ^~
Bob.cpp:171:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  171 |             if (C[i] == fx || D[i] == fx)
      |             ^~

Subtask #1
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	48408 KB	Output is correct
2	Correct	8 ms	48532 KB	Output is correct
3	Correct	8 ms	48644 KB	Output is correct
4	Correct	7 ms	46424 KB	Output is correct
5	Correct	7 ms	48644 KB	Output is correct
6	Correct	9 ms	48500 KB	Output is correct
7	Correct	8 ms	48644 KB	Output is correct
8	Correct	9 ms	48456 KB	Output is correct
9	Correct	8 ms	48564 KB	Output is correct
10	Correct	7 ms	46544 KB	Output is correct
11	Correct	8 ms	48644 KB	Output is correct
12	Correct	9 ms	48616 KB	Output is correct
13	Correct	9 ms	48640 KB	Output is correct
14	Correct	7 ms	48644 KB	Output is correct
15	Correct	8 ms	48644 KB	Output is correct
16	Correct	8 ms	48644 KB	Output is correct
17	Correct	9 ms	48440 KB	Output is correct
18	Correct	9 ms	48644 KB	Output is correct
19	Correct	8 ms	48732 KB	Output is correct
20	Correct	8 ms	48416 KB	Output is correct
21	Correct	7 ms	48644 KB	Output is correct
22	Correct	8 ms	48644 KB	Output is correct
23	Correct	9 ms	48644 KB	Output is correct
24	Correct	9 ms	46596 KB	Output is correct
25	Correct	7 ms	48640 KB	Output is correct
26	Correct	6 ms	48492 KB	Output is correct
27	Correct	8 ms	48644 KB	Output is correct
28	Correct	7 ms	48512 KB	Output is correct
29	Correct	10 ms	48644 KB	Output is correct
30	Correct	7 ms	46596 KB	Output is correct
31	Correct	7 ms	46544 KB	Output is correct
32	Correct	8 ms	46460 KB	Output is correct
33	Correct	6 ms	46588 KB	Output is correct
34	Correct	8 ms	46368 KB	Output is correct
35	Correct	7 ms	46468 KB	Output is correct
36	Correct	8 ms	48604 KB	Output is correct
37	Correct	7 ms	48644 KB	Output is correct
38	Correct	7 ms	48644 KB	Output is correct
39	Correct	7 ms	48640 KB	Output is correct
40	Correct	7 ms	48500 KB	Output is correct
41	Correct	6 ms	48604 KB	Output is correct
42	Correct	6 ms	48644 KB	Output is correct
43	Correct	6 ms	48640 KB	Output is correct
44	Correct	6 ms	46596 KB	Output is correct
45	Correct	7 ms	46596 KB	Output is correct
46	Correct	7 ms	48644 KB	Output is correct
47	Correct	6 ms	48644 KB	Output is correct
48	Correct	7 ms	48644 KB	Output is correct
49	Correct	7 ms	48644 KB	Output is correct
50	Correct	6 ms	46596 KB	Output is correct
51	Correct	7 ms	42500 KB	Output is correct
52	Correct	7 ms	48464 KB	Output is correct
53	Correct	7 ms	46596 KB	Output is correct
54	Correct	7 ms	48892 KB	Output is correct
55	Correct	8 ms	48640 KB	Output is correct
56	Correct	8 ms	48640 KB	Output is correct
57	Correct	6 ms	48748 KB	Output is correct
58	Correct	8 ms	48644 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	48408 KB	Output is correct
2	Correct	8 ms	48532 KB	Output is correct
3	Correct	8 ms	48644 KB	Output is correct
4	Correct	7 ms	46424 KB	Output is correct
5	Correct	7 ms	48644 KB	Output is correct
6	Correct	9 ms	48500 KB	Output is correct
7	Correct	8 ms	48644 KB	Output is correct
8	Correct	9 ms	48456 KB	Output is correct
9	Correct	8 ms	48564 KB	Output is correct
10	Correct	7 ms	46544 KB	Output is correct
11	Correct	8 ms	48644 KB	Output is correct
12	Correct	9 ms	48616 KB	Output is correct
13	Correct	9 ms	48640 KB	Output is correct
14	Correct	7 ms	48644 KB	Output is correct
15	Correct	8 ms	48644 KB	Output is correct
16	Correct	8 ms	48644 KB	Output is correct
17	Correct	9 ms	48440 KB	Output is correct
18	Correct	9 ms	48644 KB	Output is correct
19	Correct	8 ms	48732 KB	Output is correct
20	Correct	8 ms	48416 KB	Output is correct
21	Correct	7 ms	48644 KB	Output is correct
22	Correct	8 ms	48644 KB	Output is correct
23	Correct	9 ms	48644 KB	Output is correct
24	Correct	9 ms	46596 KB	Output is correct
25	Correct	7 ms	48640 KB	Output is correct
26	Correct	6 ms	48492 KB	Output is correct
27	Correct	8 ms	48644 KB	Output is correct
28	Correct	7 ms	48512 KB	Output is correct
29	Correct	10 ms	48644 KB	Output is correct
30	Correct	7 ms	46596 KB	Output is correct
31	Correct	7 ms	46544 KB	Output is correct
32	Correct	8 ms	46460 KB	Output is correct
33	Correct	6 ms	46588 KB	Output is correct
34	Correct	8 ms	46368 KB	Output is correct
35	Correct	7 ms	46468 KB	Output is correct
36	Correct	8 ms	48604 KB	Output is correct
37	Correct	7 ms	48644 KB	Output is correct
38	Correct	7 ms	48644 KB	Output is correct
39	Correct	7 ms	48640 KB	Output is correct
40	Correct	7 ms	48500 KB	Output is correct
41	Correct	6 ms	48604 KB	Output is correct
42	Correct	6 ms	48644 KB	Output is correct
43	Correct	6 ms	48640 KB	Output is correct
44	Correct	6 ms	46596 KB	Output is correct
45	Correct	7 ms	46596 KB	Output is correct
46	Correct	7 ms	48644 KB	Output is correct
47	Correct	6 ms	48644 KB	Output is correct
48	Correct	7 ms	48644 KB	Output is correct
49	Correct	7 ms	48644 KB	Output is correct
50	Correct	6 ms	46596 KB	Output is correct
51	Correct	7 ms	42500 KB	Output is correct
52	Correct	7 ms	48464 KB	Output is correct
53	Correct	7 ms	46596 KB	Output is correct
54	Correct	7 ms	48892 KB	Output is correct
55	Correct	8 ms	48640 KB	Output is correct
56	Correct	8 ms	48640 KB	Output is correct
57	Correct	6 ms	48748 KB	Output is correct
58	Correct	8 ms	48644 KB	Output is correct
59	Correct	7 ms	48520 KB	Output is correct
60	Correct	8 ms	48644 KB	Output is correct
61	Correct	7 ms	48644 KB	Output is correct
62	Correct	8 ms	48640 KB	Output is correct
63	Correct	6 ms	48644 KB	Output is correct
64	Correct	8 ms	48644 KB	Output is correct
65	Correct	8 ms	48648 KB	Output is correct
66	Correct	7 ms	48640 KB	Output is correct
67	Correct	9 ms	48572 KB	Output is correct
68	Correct	6 ms	48644 KB	Output is correct
69	Correct	7 ms	48644 KB	Output is correct
70	Correct	8 ms	48644 KB	Output is correct
71	Correct	8 ms	48640 KB	Output is correct
72	Correct	8 ms	48652 KB	Output is correct
73	Correct	8 ms	48644 KB	Output is correct
74	Correct	7 ms	48640 KB	Output is correct
75	Correct	7 ms	48640 KB	Output is correct
76	Correct	7 ms	48644 KB	Output is correct
77	Correct	8 ms	48640 KB	Output is correct
78	Correct	8 ms	48644 KB	Output is correct
79	Correct	8 ms	48636 KB	Output is correct
80	Correct	7 ms	48652 KB	Output is correct
81	Correct	7 ms	48644 KB	Output is correct
82	Correct	8 ms	48644 KB	Output is correct
83	Correct	8 ms	48644 KB	Output is correct
84	Correct	8 ms	48640 KB	Output is correct
85	Correct	9 ms	48640 KB	Output is correct
86	Correct	8 ms	48644 KB	Output is correct
87	Correct	8 ms	48652 KB	Output is correct
88	Correct	8 ms	48616 KB	Output is correct
89	Correct	6 ms	46592 KB	Output is correct
90	Correct	9 ms	46528 KB	Output is correct
91	Correct	8 ms	46452 KB	Output is correct
92	Correct	7 ms	46592 KB	Output is correct
93	Correct	7 ms	46596 KB	Output is correct
94	Correct	8 ms	48652 KB	Output is correct
95	Correct	8 ms	48640 KB	Output is correct
96	Correct	8 ms	48644 KB	Output is correct
97	Correct	8 ms	48640 KB	Output is correct
98	Correct	8 ms	48616 KB	Output is correct
99	Correct	7 ms	48644 KB	Output is correct
100	Correct	7 ms	48648 KB	Output is correct
101	Correct	7 ms	48644 KB	Output is correct
102	Correct	6 ms	46596 KB	Output is correct
103	Correct	7 ms	48640 KB	Output is correct
104	Correct	8 ms	48644 KB	Output is correct
105	Correct	8 ms	48464 KB	Output is correct
106	Correct	9 ms	48556 KB	Output is correct
107	Correct	7 ms	48644 KB	Output is correct
108	Correct	6 ms	48644 KB	Output is correct
109	Correct	7 ms	48644 KB	Output is correct
110	Correct	7 ms	48640 KB	Output is correct
111	Correct	8 ms	48512 KB	Output is correct
112	Correct	7 ms	48644 KB	Output is correct
113	Correct	7 ms	48644 KB	Output is correct
114	Correct	8 ms	48644 KB	Output is correct
115	Correct	8 ms	48736 KB	Output is correct
116	Correct	7 ms	48640 KB	Output is correct
117	Correct	7 ms	48644 KB	Output is correct
118	Correct	6 ms	48728 KB	Output is correct

Subtask #3
0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	71032 KB	Output is correct : V - N = 12
2	Correct	336 ms	71340 KB	Output is correct : V - N = 12
3	Correct	141 ms	54296 KB	Output is correct : V - N = 12
4	Correct	12 ms	49092 KB	Output is correct : V - N = 12
5	Correct	74 ms	51628 KB	Output is correct : V - N = 12
6	Correct	241 ms	70608 KB	Output is correct : V - N = 12
7	Correct	379 ms	72824 KB	Output is correct : V - N = 12
8	Correct	342 ms	71420 KB	Output is correct : V - N = 12
9	Correct	183 ms	55012 KB	Output is correct : V - N = 12
10	Correct	24 ms	49704 KB	Output is correct : V - N = 12
11	Correct	37 ms	50088 KB	Output is correct : V - N = 12
12	Correct	191 ms	60556 KB	Output is correct : V - N = 12
13	Correct	389 ms	71740 KB	Output is correct : V - N = 12
14	Correct	420 ms	71884 KB	Output is correct : V - N = 12
15	Correct	220 ms	66428 KB	Output is correct : V - N = 12
16	Correct	55 ms	50616 KB	Output is correct : V - N = 12
17	Correct	16 ms	49400 KB	Output is correct : V - N = 12
18	Correct	147 ms	54604 KB	Output is correct : V - N = 12
19	Correct	305 ms	71552 KB	Output is correct : V - N = 12
20	Correct	394 ms	72088 KB	Output is correct : V - N = 12
21	Correct	104 ms	53144 KB	Output is correct : V - N = 12
22	Correct	75 ms	51872 KB	Output is correct : V - N = 12
23	Correct	33 ms	50168 KB	Output is correct : V - N = 12
24	Correct	9 ms	48596 KB	Output is correct : V - N = 12
25	Correct	25 ms	49724 KB	Output is correct : V - N = 12
26	Correct	63 ms	51600 KB	Output is correct : V - N = 12
27	Correct	103 ms	52116 KB	Output is correct : V - N = 12
28	Correct	89 ms	51868 KB	Output is correct : V - N = 12
29	Correct	54 ms	50104 KB	Output is correct : V - N = 12
30	Correct	13 ms	48912 KB	Output is correct : V - N = 12
31	Correct	10 ms	46596 KB	Output is correct : V - N = 12
32	Correct	11 ms	46544 KB	Output is correct : V - N = 12
33	Correct	11 ms	46752 KB	Output is correct : V - N = 12
34	Correct	9 ms	46592 KB	Output is correct : V - N = 12
35	Correct	10 ms	46604 KB	Output is correct : V - N = 12
36	Correct	388 ms	71824 KB	Output is correct : V - N = 12
37	Runtime error	395 ms	109332 KB	Execution killed with signal 6
38	Halted	0 ms	0 KB	-

Submission #991844

Compilation message

Subtask #1 22.0 / 22.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 63.0

Subtask #1
22.0 / 22.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 63.0