#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
vector <int> x , y , w[400010];
int v[400010] , elem , newp[400010] , previous;
void dfs (int nod , int conf , int p2 , int val , vector<int> a){
int i , vecin , cnt;
if (2 * nod > val){
if (conf < a.size())
w[nod].push_back(-a[conf]);
else if (conf == val){
w[nod].push_back(0);
//previous = nod;
}
else w[nod].push_back(1);
if (conf + p2 < a.size())
w[nod].push_back(-a[conf]);
else if (conf + p2 == val){
w[nod].push_back(0);
//previous = nod;
}
else w[nod].push_back(1);
/// altfel, e o frunza irelevanta
}
else {
dfs(2 * nod , conf , p2 * 2 , val , a);
dfs(2 * nod + 1 , conf + p2 , p2 * 2 , val , a);
/// aici trb sa vad daca elimin vreun fiu
/*cnt = 0;
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (w[vecin].size() == 1){ /// vecin e useless
cnt++;
}
else if (w[vecin].empty()) {
printf ("nu ma asteptam la asta:)");
}
}
if (cnt == 2){ /// elimini ambele
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (w[vecin].size() == 1){ /// vecin e useless
w[nod][i] = w[vecin][0];
}
else if (w[vecin].empty()) {
printf ("nu ma asteptam la asta:)");
}
}
}
else if (cnt == 1){
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (w[vecin].size() == 1){ /// vecin e useless, dar nu poti sa il elim
w[ vecin ].push_back(0);
if (w[previous][0] == 0)
w[previous][0] = -1;
else w[previous[1] = -1;
previous = vecin;
}
else if (w[vecin].empty()) {
printf ("nu ma asteptam la asta:)");
}
}
}*/
}
}
void dfs_put (int nod){
int i , vecin;
if (nod < 1){
return;
}
v[++elem] = nod;
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin != 1)
dfs_put(vecin);
}
}
void dfs_solve (int nod){
int i , vecin , val;
if (nod < 1){
return;
}
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin > 0)
vecin = newp[vecin];
val = -vecin;
if (i == 0)
x[ newp[nod] - 1 ] = val;
else y[ newp[nod] - 1 ] = val;
if (vecin != 1)
dfs_solve(vecin);
}
//if (x.size() != y.size())
// printf ("!!!!!!!");
if (w[nod].size() != 2){
printf ("w[nod] nu are size 2");
}
}
void create_circuit(int m, vector<int> a) {
int n = a.size() , i , l;
vector <int> c;
c.push_back(-1);
for (i = 1 ; i <= m ; i++)
c.push_back(-1);
/// trb sa vezi cate noduri nu iti sunt necesare
l = 0;
while ((1 << l) < n){
l++;
}
l++;
for (i = 1 ; i <= (1 << l) - 1 ; i++){
if (2 * i <= (1 << l) - 1){
w[i].push_back(2 * i);
w[i].push_back(2 * i + 1);
}
}
dfs (1 , 0 , 1 , (1 << l) - 1 , a);
dfs_put (1);
sort (v + 1 , v + elem + 1);
for (i = 1 ; i <= elem ; i++){
newp[v[i]] = i;
}
x.resize(elem , 0);
y.resize(elem , 0);
dfs_solve (1);
//for (i = 0 ; i < x.size() ; i++){
// printf ("%d %d\n" , x[i] , y[i]);
//}
answer (c , x , y);
}
Compilation message
doll.cpp: In function 'void dfs(int, int, int, int, std::vector<int>)':
doll.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if (conf < a.size())
| ~~~~~^~~~~~~~~~
doll.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if (conf + p2 < a.size())
| ~~~~~~~~~~^~~~~~~~~~
doll.cpp:12:9: warning: unused variable 'i' [-Wunused-variable]
12 | int i , vecin , cnt;
| ^
doll.cpp:12:13: warning: unused variable 'vecin' [-Wunused-variable]
12 | int i , vecin , cnt;
| ^~~~~
doll.cpp:12:21: warning: unused variable 'cnt' [-Wunused-variable]
12 | int i , vecin , cnt;
| ^~~
doll.cpp: In function 'void dfs_put(int)':
doll.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (i = 0 ; i < w[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
doll.cpp: In function 'void dfs_solve(int)':
doll.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (i = 0 ; i < w[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
