Submission #240937

#	Time	Username	Problem	Language	Result	Execution time	Memory
240937		Ruxandra985	Mechanical Doll (IOI18_doll)	C++14	0 / 100	100 ms	22716 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;


int v[400010] , elem , newp[400010] , leaf , f[400010] , exists[400010];
pair < int , int > order[400010];
vector <int> w[400010] , x , y;

void dfs (int nod , int conf , int p2 , int val , int linit , int dif){

    exists[nod] = 1;

    if (2 * nod > val){ /// ar trb sa unesti cu ceva din a sau cu -1
        order[++leaf] = make_pair(conf , nod);
        order[++leaf] = make_pair(conf + (1 << p2) , nod);
        return;
    }
    else {
        if (((1 << (linit - p2 - 1)) & dif) && !f[linit - p2 - 1]){

            f[linit - p2 - 1] = 1;
            w[nod].push_back(1);
            w[nod].push_back(2 * nod + 1);

            dfs (2 * nod + 1 , conf + (1 << p2) , p2 + 1 , val , linit , dif);

        }
        else {

            w[nod].push_back(2 * nod);
            w[nod].push_back(2 * nod + 1);

            dfs (2 * nod + 1 , conf + (1 << p2) , p2 + 1 , val , linit , dif);
            dfs (2 * nod , conf , p2 + 1 , val , linit , dif);

        }
    }

}


void dfs_put (int nod){

    int i , vecin;

    f[nod] = 1;

    v[++elem] = nod;

    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i];

        if (vecin > 0 && !f[vecin])
            dfs_put(vecin);

    }

}

void dfs_solve (int nod){

    int i , vecin , val;

    f[nod] = 1;

    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i];

        if (vecin > 0)
            val = -newp[vecin];
        else val = -vecin;

        if (i == 0)
            x[ newp[nod] - 1 ] = val;
        else y[ newp[nod] - 1 ] = val;

        if (vecin > 0 && !f[vecin])
            dfs_solve(vecin);

    }

}

void create_circuit(int m, vector<int> a) {
    int n = a.size() , i , l , poz;
    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++;
    }

    dfs (1 , 0 , 0 , (1 << l) - 1 , l , (1 << l) - n - 1);


    sort (order + 1 , order + leaf + 1);

    a.push_back(0);

    poz = 0;

    for (i = 1 ; i <= leaf ; i++){
        if (exists[ order[i].second ]){
            w[ order[i].second ].push_back(-a[poz]);
            poz++;
        }
    }


    memset ( f , 0 , sizeof(f) );

    dfs_put (1);

    sort (v + 1 , v + elem + 1);

    for (i = 1 ; i <= elem ; i++){
        newp[v[i]] = i;
    }

    memset ( f , 0 , sizeof(f) );

    x.resize(elem , 0);
    y.resize(elem , 0);

    dfs_solve(1);

    answer (c , x , y);

}

Compilation message (stderr)

doll.cpp: In function 'void dfs_put(int)':
doll.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (i = 0 ; i < w[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
doll.cpp: In function 'void dfs_solve(int)':
doll.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (i = 0 ; i < w[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56