oj.uz

Submission #289360

# Submission time Handle Problem Language Result Execution time Memory
289360 2020-09-02T15:30:10 Z alexandra_udristoiu Amusement Park (JOI17_amusement_park) C++14
10 / 100
 36 ms 4856 KB 
#include<algorithm>
#include<vector>
#include "Joi.h"
#define DIM 10005
using namespace std;
static vector<int> v[DIM];
static int d[DIM], e[DIM], c[DIM], t[DIM], viz[DIM], dj[DIM], ind[DIM];
static int nr, k;
static void dfs(int nod, int tt){
    t[nod] = tt;
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(viz[vecin] == 0){
            d[vecin] = 1 + d[nod];
            dfs(vecin, nod);
            dj[nod] = max(dj[vecin] + 1, dj[nod]);
        }
    }
}
static void dfs2(int nod){
    if(viz[nod] == -1){
        if(k == 60){
            return;
        }
        ind[nod] = k++;
    }
    int i, vecin, x;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(t[vecin] == nod && dj[vecin] == dj[nod] - 1){
            x = vecin;
            dfs2(vecin);
            break;
        }
    }
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(t[vecin] == nod && vecin != x && k != 60){
            e[++nr] = nod;
            dfs2(vecin);
        }
    }
    e[++nr] = nod;
}

void Joi(int n, int m, int a[], int b[], long long x, int aux) {
    int i, maxim = 0, nod, u;
    for(i = 0; i < m; i++){
        v[ a[i] ].push_back(b[i]);
        v[ b[i] ].push_back(a[i]);
    }
    dfs(0, -1);
    if(dj[0] + 1 >= 60){
        for(i = 0; i < n; i++){
            d[i] %= 60;
            MessageBoard(i, ( (x >> d[i]) & 1) );
        }
        return;
    }
    for(i = 0; i < n; i++){
        viz[i] = -1;
    }
    dfs2(0);
    for(i = 0; i < n; i++){
        if(viz[i] != -1){
            MessageBoard(i, ( (x >> ind[i]) & 1) );
        }
        else{
            MessageBoard(i, 0);
        }
    }
}


#include "Ioi.h"
#include<algorithm>
#include<vector>
#define DIM 10005
using namespace std;
static vector<int> v[DIM];
static int d[DIM], e[DIM], c[DIM], t[DIM], ind[DIM], dj[DIM], viz[DIM];
static int nr, k;
static void dfs(int nod, int tt){
    t[nod] = tt;
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(viz[vecin] == 0){
            d[vecin] = 1 + d[nod];
            dfs(vecin, nod);
            dj[nod] = max(dj[vecin] + 1, dj[nod]);
        }
    }
}
static void dfs2(int nod){
    if(viz[nod] == -1){
        if(k == 60){
            return;
        }
        ind[nod] = k++;
    }
    int i, vecin, x;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(t[vecin] == nod && dj[vecin] == dj[nod] - 1){
            x = vecin;
            dfs2(vecin);
            break;
        }
    }
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(t[vecin] == nod && vecin != x && k != 60){
            e[++nr] = nod;
            dfs2(vecin);
        }
    }
    e[++nr] = nod;
}

long long Ioi(int n, int m, int a[], int b[], int p, int val, int aux) {
    long long x = 0;
    int i, maxim = 0, nod, u, j;
    for(i = 0; i < m; i++){
        v[ a[i] ].push_back(b[i]);
        v[ b[i] ].push_back(a[i]);
    }
    dfs(0, -1);
    if(dj[0] + 1 >= 60){
        if(d[p] + 1 >= 60){
            d[p] %= 60;
            x += (1LL << d[p]) * val;
            for(i = 1; i < 60; i++){
                val = Move(t[p]);
                p = t[p];
                d[p] %= 60;
                x += (1LL << d[p]) * val;
            }
        }
        else{
            while(p != 0){
                val = Move(t[p]);
                p = t[p];
            }
            x += val;
            for(i = 1; i < 60; i++){
                for(j = 0; j < v[p].size(); j++){
                    if(dj[ v[p][j] ] == dj[p] - 1){
                        p = v[p][j];
                        val = Move(p);
                        x += (1LL << i) * val;
                        break;
                    }
                }
            }
        }
    }
    else{
        for(i = 0; i < n; i++){
            viz[i] = -1;
        }
        dfs2(0);
        while(p != 0){
            val = Move(t[p]);
            p = t[p];
        }
        x += val;
        for(i = nr - 1; i >= 1; i--){
            val = Move(e[i]);
            x &= (1LL << ind[ e[i] ]) * val;
        }
    }
    return x;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs2(int)':
Joi.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Joi.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:48:12: warning: unused variable 'maxim' [-Wunused-variable]
   48 |     int i, maxim = 0, nod, u;
      |            ^~~~~
Joi.cpp:48:23: warning: unused variable 'nod' [-Wunused-variable]
   48 |     int i, maxim = 0, nod, u;
      |                       ^~~
Joi.cpp:48:28: warning: unused variable 'u' [-Wunused-variable]
   48 |     int i, maxim = 0, nod, u;
      |                            ^
Joi.cpp: At global scope:
Joi.cpp:7:28: warning: 'c' defined but not used [-Wunused-variable]
    7 | static int d[DIM], e[DIM], c[DIM], t[DIM], viz[DIM], dj[DIM], ind[DIM];
      |                            ^
Joi.cpp: In function 'void dfs2(int)':
Joi.cpp:39:28: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |         if(t[vecin] == nod && vecin != x && k != 60){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int)':
Ioi.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Ioi.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:73:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for(j = 0; j < v[p].size(); j++){
      |                            ~~^~~~~~~~~~~~~
Ioi.cpp:49:12: warning: unused variable 'maxim' [-Wunused-variable]
   49 |     int i, maxim = 0, nod, u, j;
      |            ^~~~~
Ioi.cpp:49:23: warning: unused variable 'nod' [-Wunused-variable]
   49 |     int i, maxim = 0, nod, u, j;
      |                       ^~~
Ioi.cpp:49:28: warning: unused variable 'u' [-Wunused-variable]
   49 |     int i, maxim = 0, nod, u, j;
      |                            ^
Ioi.cpp: At global scope:
Ioi.cpp:7:28: warning: 'c' defined but not used [-Wunused-variable]
    7 | static int d[DIM], e[DIM], c[DIM], t[DIM], ind[DIM], dj[DIM], viz[DIM];
      |                            ^
Ioi.cpp: In function 'void dfs2(int)':
Ioi.cpp:39:28: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |         if(t[vecin] == nod && vecin != x && k != 60){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1284 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4756 KB Output is correct
2 Correct 33 ms 4764 KB Output is correct
3 Correct 36 ms 4644 KB Output is correct
4 Incorrect 17 ms 3296 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1284 KB Output is correct
2 Correct 1 ms 1156 KB Output is correct
3 Correct 2 ms 1284 KB Output is correct
4 Correct 3 ms 1572 KB Output is correct
5 Correct 5 ms 1760 KB Output is correct
6 Correct 3 ms 1572 KB Output is correct
7 Correct 3 ms 1764 KB Output is correct
8 Correct 4 ms 1744 KB Output is correct
9 Correct 18 ms 3916 KB Output is correct
10 Correct 16 ms 3840 KB Output is correct
11 Correct 15 ms 4036 KB Output is correct
12 Correct 1 ms 1156 KB Output is correct
13 Correct 2 ms 1304 KB Output is correct
14 Correct 2 ms 1284 KB Output is correct
15 Correct 2 ms 1316 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4856 KB Output is correct
2 Correct 28 ms 4644 KB Output is correct
3 Correct 28 ms 4852 KB Output is correct
4 Incorrect 17 ms 3116 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4852 KB Output is correct
2 Correct 28 ms 4644 KB Output is correct
3 Correct 28 ms 4848 KB Output is correct
4 Incorrect 18 ms 3276 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -