제출 #289485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289485		alexandra_udristoiu	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	44 ms	4604 KiB

Joi

#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, int tip){
    if(ind[nod] == -1){
        if(k == 60){
            return;
        }
        ind[nod] = k++;
    }
    int i, vecin, x = -1;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(t[vecin] == nod && dj[vecin] == dj[nod] - 1 && tip == 0){
            x = vecin;
            dfs2(vecin, tip);
            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, 1);
        }
    }
    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++){
        ind[i] = -1;
    }
    dfs2(0, 0);
    for(i = 0; i < n; i++){
        if(ind[i] != -1){
            MessageBoard(i, ( (x >> ind[i]) & 1) );
        }
        else{
            MessageBoard(i, 0);
        }
    }
}

Ioi

#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, int tip){
    if(ind[nod] == -1){
        if(k == 60){
            return;
        }
        ind[nod] = k++;
    }
    int i, vecin, x = -1;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(t[vecin] == nod && dj[vecin] == dj[nod] - 1 && tip == 0){
            x = vecin;
            dfs2(vecin, tip);
            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, 1);
        }
    }
    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++){
            ind[i] = -1;
        }
        dfs2(0, 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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, 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];
      |                            ^

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, 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];
      |                            ^

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17