#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, m;
vector < int > g[maxn];
vector < int > c, x, y;
struct state
{
int dev, lf_child, rf_child;
vector < int > fin;
state()
{
dev = 0;
lf_child = rf_child = -1;
fin.clear();
}
};
void create_node(int v)
{
if (g[v].size() == 0)
return;
if (g[v].size() == 1)
{
c[v] = g[v][0];
return;
}
int nec = 2, st = 0;
while(nec < g[v].size())
nec *= 2, st ++;
///cout << g[v].size() << " " << nec << " : " << st << endl;
vector < state > gen;
int sz = x.size();
state it;
it.dev = ++ sz;
c[v] = -it.dev;
it.fin.push_back(1);
gen.push_back(it);
for (int step = 0; step < st; step ++)
{
vector < state > new_gen;
for (int i = 0; i < gen.size(); i ++)
{
state new_state;
new_state.dev = ++ sz;
gen[i].lf_child = - new_state.dev;
for (int cur : gen[i].fin)
new_state.fin.push_back(cur);
new_gen.push_back(new_state);
new_state = state();
new_state.dev = ++ sz;
gen[i].rf_child = - new_state.dev;
for (int cur : gen[i].fin)
new_state.fin.push_back(cur + (1 << step));
new_gen.push_back(new_state);
}
for (state cur : gen)
{
x.push_back(cur.lf_child);
y.push_back(cur.rf_child);
}
gen = new_gen;
}
///cout << "fine" << endl;
int offset = gen.size() * 2 - g[v].size();
for (int i = 0; i < gen.size(); i ++)
{
///cout << gen[i].fin.size() << endl;
int lf_path = gen[i].fin[0], rf_path = gen[i].fin[0] + (1 << st);
///cout << v << " :: " << lf_path << " : " << rf_path << endl;
if (lf_path > offset)
x.push_back(g[v][lf_path - offset - 1]);
else
x.push_back(- it.dev);
if (rf_path > offset)
y.push_back(g[v][rf_path - offset - 1]);
else
y.push_back(-it.dev);
}
}
void create_circuit(int M, vector<int> A)
{
n = A.size();
m = M;
c.resize(m + 1);
g[0].push_back(A[0]);
for (int i = 1; i < A.size(); i ++)
{
g[0].push_back(A[i]);
}
g[0].push_back(0);
create_node(0);
for (int i = 0; i <= m; i ++)
c[i] = -1;
/**for (int i = 0; i <= m; i ++)
{
create_node(i);
continue;
}*/
/**for (int i = 0; i <= m; i ++)
cout << c[i] << " ";
cout << endl;
for (int i = 0; i < x.size(); i ++)
cout << x[i] << " " << y[i] << endl;*/
answer(c, x, y);
}
Compilation message
doll.cpp: In function 'void create_node(int)':
doll.cpp:27:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
27 | if (g[v].size() == 0)
| ^~
doll.cpp:30:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
30 | if (g[v].size() == 1)
| ^~
doll.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(nec < g[v].size())
| ~~~~^~~~~~~~~~~~~
doll.cpp:49:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < gen.size(); i ++)
| ~~^~~~~~~~~~~~
doll.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < gen.size(); i ++)
| ~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 1; i < A.size(); i ++)
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 2 |
Partially correct |
111 ms |
30656 KB |
Output is partially correct |
| 3 |
Partially correct |
99 ms |
30652 KB |
Output is partially correct |
| 4 |
Partially correct |
104 ms |
31452 KB |
Output is partially correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
2 ms |
4948 KB |
Output is partially correct |
| 2 |
Partially correct |
111 ms |
30656 KB |
Output is partially correct |
| 3 |
Partially correct |
99 ms |
30652 KB |
Output is partially correct |
| 4 |
Partially correct |
104 ms |
31452 KB |
Output is partially correct |
| 5 |
Partially correct |
124 ms |
31616 KB |
Output is partially correct |
| 6 |
Partially correct |
111 ms |
31500 KB |
Output is partially correct |
| 7 |
Partially correct |
115 ms |
31476 KB |
Output is partially correct |
| 8 |
Partially correct |
109 ms |
31512 KB |
Output is partially correct |
| 9 |
Partially correct |
119 ms |
30556 KB |
Output is partially correct |
| 10 |
Partially correct |
112 ms |
31480 KB |
Output is partially correct |
| 11 |
Partially correct |
134 ms |
31420 KB |
Output is partially correct |
| 12 |
Partially correct |
102 ms |
30656 KB |
Output is partially correct |
| 13 |
Partially correct |
99 ms |
30804 KB |
Output is partially correct |
| 14 |
Partially correct |
99 ms |
30636 KB |
Output is partially correct |
| 15 |
Partially correct |
107 ms |
30656 KB |
Output is partially correct |
| 16 |
Partially correct |
5 ms |
5716 KB |
Output is partially correct |
| 17 |
Correct |
59 ms |
18552 KB |
Output is correct |
| 18 |
Partially correct |
99 ms |
30632 KB |
Output is partially correct |
| 19 |
Partially correct |
99 ms |
30648 KB |
Output is partially correct |
| 20 |
Partially correct |
110 ms |
31464 KB |
Output is partially correct |
| 21 |
Partially correct |
130 ms |
31464 KB |
Output is partially correct |
| 22 |
Partially correct |
102 ms |
31404 KB |
Output is partially correct |
