oj.uz

Submission #289356

# Submission time Handle Problem Language Result Execution time Memory
289356 2020-09-02T15:26:17 Z alexandra_udristoiu Amusement Park (JOI17_amusement_park) C++14
10 / 100
 210 ms 262148 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];
static int nr, k;
static void dfs(int nod, int tt){
    t[nod] = tt;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(vecin != tt){
            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;
        }
        viz[nod] = k++;
    }
    int i, vecin, x;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(vecin != t[nod] && dj[vecin] == dj[nod] - 1){
            x = vecin;
            dfs2(vecin);
            break;
        }
    }
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(vecin != t[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 >> viz[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], viz[DIM], dj[DIM];
static int nr, k;
static void dfs(int nod, int tt){
    t[nod] = tt;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(vecin != tt){
            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;
        }
        viz[nod] = k++;
    }
    int i, vecin, x;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(vecin != t[nod] && dj[vecin] == dj[nod] - 1){
            x = vecin;
            dfs2(vecin);
            break;
        }
    }
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(vecin != t[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 << viz[ e[i] ]) * val;
        }
    }
    return x;
}

Compilation message

Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs2(int)':
Joi.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Joi.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:47:12: warning: unused variable 'maxim' [-Wunused-variable]
   47 |     int i, maxim = 0, nod, u;
      |            ^~~~~
Joi.cpp:47:23: warning: unused variable 'nod' [-Wunused-variable]
   47 |     int i, maxim = 0, nod, u;
      |                       ^~~
Joi.cpp:47:28: warning: unused variable 'u' [-Wunused-variable]
   47 |     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];
      |                            ^
Joi.cpp: In function 'void dfs2(int)':
Joi.cpp:38:28: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         if(vecin != t[nod] && vecin != x && k != 60){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs2(int)':
Ioi.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(i = 0; i < v[nod].size(); i++){
      |                ~~^~~~~~~~~~~~~~~
Ioi.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     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:72:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for(j = 0; j < v[p].size(); j++){
      |                            ~~^~~~~~~~~~~~~
Ioi.cpp:48:12: warning: unused variable 'maxim' [-Wunused-variable]
   48 |     int i, maxim = 0, nod, u, j;
      |            ^~~~~
Ioi.cpp:48:23: warning: unused variable 'nod' [-Wunused-variable]
   48 |     int i, maxim = 0, nod, u, j;
      |                       ^~~
Ioi.cpp:48:28: warning: unused variable 'u' [-Wunused-variable]
   48 |     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], viz[DIM], dj[DIM];
      |                            ^
Ioi.cpp: In function 'void dfs2(int)':
Ioi.cpp:38:28: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         if(vecin != t[nod] && vecin != x && k != 60){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 179 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1160 KB Output is correct
2 Correct 2 ms 1296 KB Output is correct
3 Correct 2 ms 1160 KB Output is correct
4 Correct 3 ms 1740 KB Output is correct
5 Correct 3 ms 1716 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1588 KB Output is correct
8 Correct 4 ms 1588 KB Output is correct
9 Correct 15 ms 4308 KB Output is correct
10 Correct 14 ms 4316 KB Output is correct
11 Correct 17 ms 4240 KB Output is correct
12 Correct 1 ms 1288 KB Output is correct
13 Correct 1 ms 1160 KB Output is correct
14 Correct 1 ms 1288 KB Output is correct
15 Correct 2 ms 1160 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -