oj.uz

답안 #590599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590599 2022-07-06T07:20:37 Z 조영욱(#8414) Amusement Park (JOI17_amusement_park) C++14
0 / 100
 10 ms 2404 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

int n,m;
long long x;
int t;
int arr[10000];
int p[10000];
vector<int> adj[10000];
typedef pair<int,int> P;
int dist[10000];

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}

P longest() {
    memset(dist,-1,sizeof(dist));
    queue<int> q;
    q.push(0);
    dist[0]=0;
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (dist[nt]==-1) {
                dist[nt]=dist[now]+1;
                q.push(nt);
            }
        }
    }
    int pos=0;
    for(int i=1;i<n;i++) {
        if (dist[i]>dist[pos]) {
            pos=i;
        }
    }
    memset(dist,-1,sizeof(dist));
    dist[pos]=0;
    q.push(pos);
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (dist[nt]==-1) {
                dist[nt]=dist[now]+1;
                q.push(nt);
            }
        }
    }
    int pos1=0;
    for(int i=1;i<n;i++) {
        if (dist[i]>dist[pos1]) {
            pos1=i;
        }
    }
    return P(pos,dist[pos1]);
}

int f=0;

void dfs0(int v,int d,int prev) {
    int now=d%60;
    if (x&(1LL<<now)) {
        MessageBoard(v,1);
    }
    else {
        MessageBoard(v,0);
    }
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        dfs0(nt,d+1,v);
    }
}

void dfs1(int v,int prev) {
    if (f>=60) {
        MessageBoard(v,0);
    }
    else {
        if (x&(1LL<<f)) {
            MessageBoard(v,1);
        }
        else {
            MessageBoard(v,0);
        }
    }
    f++;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        dfs1(nt,v);
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    n=N;
    m=M;
    x=X;
    t=T;
    memset(p,-1,sizeof(p));
    for(int i=0;i<m;i++) {
        if (find(A[i])!=find(B[i])) {
            adj[A[i]].push_back(B[i]);
            adj[B[i]].push_back(A[i]);
            merge(A[i],B[i]);
        }
    }
    P got=longest();
    if (got.second>=59) {
        assert(got.first==n-1);
        assert(got.second==n-1);
        dfs0(got.first,0,-1);
        //assert(false);
    }
    else {
        assert(t!=3);
        dfs1(0,-1);
    }
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int m;
int st,val,t;
int p[10000];
vector<int> adj[10000];
int dist[10000];
typedef pair<int,int> P;

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}

P longest() {
    memset(dist,-1,sizeof(dist));
    queue<int> q;
    q.push(0);
    dist[0]=0;
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (dist[nt]==-1) {
                dist[nt]=dist[now]+1;
                q.push(nt);
            }
        }
    }
    int pos=0;
    for(int i=1;i<n;i++) {
        if (dist[i]>dist[pos]) {
            pos=i;
        }
    }
    memset(dist,-1,sizeof(dist));
    dist[pos]=0;
    q.push(pos);
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (dist[nt]==-1) {
                dist[nt]=dist[now]+1;
                q.push(nt);
            }
        }
    }
    int pos1=0;
    for(int i=1;i<n;i++) {
        if (dist[i]>dist[pos1]) {
            pos1=i;
        }
    }
    return P(pos,dist[pos1]);
}

int par[10000];
int dep[10000];

void dfs(int v,int prev) {
    par[v]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt!=prev) {
            dep[nt]=dep[v]+1;
            dfs(nt,v);
        }
    }
}

int f=0;

long long dfs1(int v,int prev) {
    long long ret=0;
    if (f<60)
        ret+=(((long long)val)<<f);
    f++;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        bool flag=(f<=59);
        if (flag) {
            val=Move(nt);
        }
        ret+=dfs1(nt,v);
        if (flag) {
            val=Move(v);
        }
    }
    return ret;
}

long long Ioi(int N, int M, int A[], int B[], int PP, int V, int T) {
    n=N;
    m=M;
    st=PP;
    val=V;
    t=T;
    memset(p,-1,sizeof(p));
    for(int i=0;i<m;i++) {
        if (find(A[i])!=find(B[i])) {
            adj[A[i]].push_back(B[i]);
            adj[B[i]].push_back(A[i]);
            merge(A[i],B[i]);
        }
    }
    P got=longest();
    if (got.second>=59) {
        assert(got.first==n-1);
        assert(got.second==n-1);
        dfs(got.first,-1);
        while (dep[st]%60!=0) {
            assert(par[st]==st+1);
            val=Move(par[st]);
            st=par[st];
        }
        long long ret=0;
        for(int i=0;i<60;i++) {
            ret+=(((long long)val)<<i);
            if (i==59) {
                break;
            }
            for(int j=0;j<adj[st].size();j++) {
                int nt=adj[st][j];
                if (nt!=par[st]) {
                    assert(nt==st-1);
                    val=Move(nt);
                    st=nt;
                    break;
                }
            }
        }
        return ret;
    }
    else {
        assert(t!=3);
        dfs(0,-1);
        while (st!=0) {
            val=Move(par[st]);
            st=par[st];
        }
        return dfs1(0,-1);
    }
    return 0LL;
}

Compilation message

Joi.cpp: In function 'P longest()':
Joi.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Joi.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs0(int, int, int)':
Joi.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs1(int, int)':
Joi.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~

Ioi.cpp: In function 'P longest()':
Ioi.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Ioi.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int dfs1(int, int)':
Ioi.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:139:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for(int j=0;j<adj[st].size();j++) {
      |                         ~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 2 ms 1288 KB Output is correct
3 Correct 2 ms 1292 KB Output is correct
4 Runtime error 1 ms 1108 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 2404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1280 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 2388 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 2404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -