oj.uz

Submission #240940

# Submission time Handle Problem Language Result Execution time Memory
240940 2020-06-21T15:57:40 Z Ruxandra985 Mechanical Doll (IOI18_doll) C++14
100 / 100
 200 ms 30692 KB 
#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
        if (!  (((1 << (linit - p2 - 1)) & dif) && !f[linit - p2 - 1])  )
            order[++leaf] = make_pair(conf , nod);
        else {
            f[linit - p2 - 1] = 1;
            w[nod].push_back(1);
        }
        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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 61 ms 17964 KB Output is correct
3 Correct 68 ms 17964 KB Output is correct
4 Correct 9 ms 11212 KB Output is correct
5 Correct 25 ms 12572 KB Output is correct
6 Correct 91 ms 21464 KB Output is correct
7 Correct 12 ms 11284 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 61 ms 17964 KB Output is correct
3 Correct 68 ms 17964 KB Output is correct
4 Correct 9 ms 11212 KB Output is correct
5 Correct 25 ms 12572 KB Output is correct
6 Correct 91 ms 21464 KB Output is correct
7 Correct 12 ms 11284 KB Output is correct
8 Correct 118 ms 24000 KB Output is correct
9 Correct 123 ms 24300 KB Output is correct
10 Correct 181 ms 30692 KB Output is correct
11 Correct 8 ms 11280 KB Output is correct
12 Correct 12 ms 11212 KB Output is correct
13 Correct 15 ms 11160 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11212 KB Output is correct
2 Correct 61 ms 17964 KB Output is correct
3 Correct 68 ms 17964 KB Output is correct
4 Correct 9 ms 11212 KB Output is correct
5 Correct 25 ms 12572 KB Output is correct
6 Correct 91 ms 21464 KB Output is correct
7 Correct 12 ms 11284 KB Output is correct
8 Correct 118 ms 24000 KB Output is correct
9 Correct 123 ms 24300 KB Output is correct
10 Correct 181 ms 30692 KB Output is correct
11 Correct 8 ms 11280 KB Output is correct
12 Correct 12 ms 11212 KB Output is correct
13 Correct 15 ms 11160 KB Output is correct
14 Correct 166 ms 30300 KB Output is correct
15 Correct 109 ms 23604 KB Output is correct
16 Correct 160 ms 30168 KB Output is correct
17 Correct 9 ms 11164 KB Output is correct
18 Correct 9 ms 11252 KB Output is correct
19 Correct 11 ms 11212 KB Output is correct
20 Correct 195 ms 30396 KB Output is correct
21 Correct 13 ms 11204 KB Output is correct
22 Correct 10 ms 11212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11212 KB Output is correct
2 Correct 9 ms 11212 KB Output is correct
3 Correct 11 ms 11264 KB Output is correct
4 Correct 8 ms 11212 KB Output is correct
5 Correct 9 ms 11280 KB Output is correct
6 Correct 8 ms 11212 KB Output is correct
7 Correct 7 ms 11212 KB Output is correct
8 Correct 8 ms 11276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11260 KB Output is correct
2 Correct 129 ms 22680 KB Output is correct
3 Correct 100 ms 22712 KB Output is correct
4 Correct 165 ms 28868 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11260 KB Output is correct
2 Correct 129 ms 22680 KB Output is correct
3 Correct 100 ms 22712 KB Output is correct
4 Correct 165 ms 28868 KB Output is correct
5 Correct 176 ms 30016 KB Output is correct
6 Correct 197 ms 29760 KB Output is correct
7 Correct 197 ms 29792 KB Output is correct
8 Correct 159 ms 29564 KB Output is correct
9 Correct 113 ms 22720 KB Output is correct
10 Correct 168 ms 29576 KB Output is correct
11 Correct 160 ms 29136 KB Output is correct
12 Correct 118 ms 23024 KB Output is correct
13 Correct 120 ms 23400 KB Output is correct
14 Correct 106 ms 23440 KB Output is correct
15 Correct 113 ms 23508 KB Output is correct
16 Correct 15 ms 11676 KB Output is correct
17 Correct 107 ms 22872 KB Output is correct
18 Correct 136 ms 22936 KB Output is correct
19 Correct 102 ms 22968 KB Output is correct
20 Correct 200 ms 29472 KB Output is correct
21 Correct 161 ms 29152 KB Output is correct
22 Correct 196 ms 29216 KB Output is correct