oj.uz

Submission #197223

# Submission time Handle Problem Language Result Execution time Memory
197223 2020-01-19T17:30:35 Z stefdasca Mechanical Doll (IOI18_doll) C++14
6 / 100
 105 ms 14416 KB 
#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

vector<int> adj[100002];
int adja[200002], adjb[200002];

int ord[200002];
bool state[200002];
int nxt;
void dfs(int nod, int rem)
{
    if(rem == 0)
        return;
    --rem;
    if(rem)
    {
        ++nxt;
        adja[-ord[nod]] = ord[nxt];
        dfs(nxt, rem/2 + rem%2);
    }
    if(rem >= 2)
    {
        ++nxt;
        adjb[-ord[nod]] = ord[nxt];
        dfs(nxt, rem / 2);
    }
}
void dfs2(int nod, int val)
{
    if(state[-ord[nod]] == 0)
    {
        state[-ord[nod]] = 1;
        if(!adja[-ord[nod]])
        {
            adja[-ord[nod]] = val;
            return;
        }
        else
            dfs2(-adja[-ord[nod]], val);
    }
    else
    {
        state[-ord[nod]] = 0;
        if(!adjb[-ord[nod]])
        {
            adjb[-ord[nod]] = val;
            return;
        }
        else
            dfs2(-adjb[-ord[nod]], val);
    }
}
void build(int nod, int &fi)
{
    for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
        ord[i] = i * (-1);
    nxt = fi + 1;
    dfs(fi + 1, adj[nod].size() - 1);
    for(int i = 0; i < adj[nod].size(); ++i)
        dfs2(fi + 1, adj[nod][i]);
    int xtr = 0;
    for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
        if(state[i] && adjb[i] > 0)
        {
            ++xtr;
            int old = adjb[i];
            adjb[i] = -(fi + adj[nod].size() - 1 + xtr);
            adja[fi + adj[nod].size() - 1 + xtr] = -(fi + adj[nod].size() - 1 + xtr);
            adjb[fi + adj[nod].size() - 1 + xtr] = old;
        }
    fi += adj[nod].size() - 1;
    fi += xtr;
}
void create_circuit(int M, vector<int> A)
{
    int N = A.size();
    vector<int> C(M + 1);
    C[0] = A[0];
    for(int i = 0; i < A.size(); ++i)
    {
        if(i + 1 == A.size())
            adj[A[i]].push_back(0);
        else
            adj[A[i]].push_back(A[i+1]);
    }
    int sw = 0;
    for(int i = 1; i <= M; ++i)
    {
        if(adj[i].size() == 0)
            C[i] = 0;
        else
            if(adj[i].size() == 1)
                C[i] = adj[i][0];
            else
            {
                C[i] = -(sw + 1);
                build(i, sw);
            }
    }
    vector<int> X(sw), Y(sw);
    for(int k = 0; k < sw; ++k)
    {
        X[k] = adja[k + 1];
        Y[k] = adjb[k + 1];
    }
    /*
    for(int i = 0; i <= M; ++i)
        cout << C[i] << " ";
    cout << '\n';
    for(int k = 0; k < sw; ++k)
        cout << X[k] << " " << Y[k] << '\n';
    */
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void build(int, int&)':
doll.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < adj[nod].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~
doll.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0; i < A.size(); ++i)
      |                    ~~^~~~~~~~~~
doll.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if(i + 1 == A.size())
      |            ~~~~~~^~~~~~~~~~~
doll.cpp:78:9: warning: unused variable 'N' [-Wunused-variable]
   78 |     int N = A.size();
      |         ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 36 ms 6316 KB Output is correct
3 Correct 25 ms 5964 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 39 ms 7656 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 36 ms 6316 KB Output is correct
3 Correct 25 ms 5964 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 39 ms 7656 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 60 ms 8792 KB Output is correct
9 Correct 74 ms 9188 KB Output is correct
10 Correct 102 ms 12092 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 36 ms 6316 KB Output is correct
3 Correct 25 ms 5964 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 39 ms 7656 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 60 ms 8792 KB Output is correct
9 Correct 74 ms 9188 KB Output is correct
10 Correct 102 ms 12092 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Incorrect 105 ms 14416 KB state 'Y'
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB state 'Y'
2 Halted 0 ms 0 KB -