oj.uz

답안 #590723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590723 2022-07-06T09:23:52 Z 조영욱(#8414) Amusement Park (JOI17_amusement_park) C++14
10 / 100
 28 ms 4172 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);
            }
        }
    }
    for(int i=0;i<n;i++){
        arr[i]+=dist[i];
    }
    int pos1=0;
    for(int i=1;i<n;i++) {
        if (dist[i]>dist[pos1]) {
            pos1=i;
        }
    }
    P ret=P(pos,dist[pos1]);
    memset(dist,-1,sizeof(dist));
    dist[pos1]=0;
    q.push(pos1);
    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);
            }
        }
    }
    for(int i=0;i<n;i++){
        arr[i]+=dist[i];
    }
    return ret;
}

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;
        }
        //assert(nt==v-1);
        dfs0(nt,d+1,v);
    }
}

void dfs1(int v,int prev) {
    int now=f%60;
    if (x&(1LL<<now)) {
        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) {
        dfs0(got.first,0,-1);
    }
    else {
        int c=-1;
        for(int i=0;i<n;i++) {
            if (arr[i]==got.second&&dist[i]==got.second/2) {
                c=i;
                break;
            }
        }
        assert(c!=-1);
        dfs1(c,-1);
    }
}

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

int n;
int m;
int st,val,t;
int p[10000];
int arr[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);
            }
        }
    }
    for(int i=0;i<n;i++){
        arr[i]+=dist[i];
    }
    int pos1=0;
    for(int i=1;i<n;i++) {
        if (dist[i]>dist[pos1]) {
            pos1=i;
        }
    }
    P ret=P(pos,dist[pos1]);
    memset(dist,-1,sizeof(dist));
    dist[pos1]=0;
    q.push(pos1);
    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);
            }
        }
    }
    for(int i=0;i<n;i++){
        arr[i]+=dist[i];
    }
    return ret;
}

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

void dfs(int v,int prev) {
    par[v]=prev;
    md[v]=dep[v];
    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);
            md[v]=max(md[v],md[nt]);
        }
    }
}

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);
        if (dep[st]>=59) {
            long long ret=0;
            for(int i=0;i<60;i++) {
                ret+=(((long long)val)<<(dep[st]%60));
                if (i==59) {
                    break;
                }
                val=Move(par[st]);
                st=par[st];
            }
            return ret;
        }
        while (st!=got.first) {
            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]&&md[st]>=59) {
                    val=Move(nt);
                    st=nt;
                }
            }
        }
        return ret;
    }
    else {
        int c=-1;
        for(int i=0;i<n;i++) {
            if (arr[i]==got.second&&dist[i]==got.second/2) {
                c=i;
                break;
            }
        }
        assert(c!=-1);
        dfs(c,-1);
        while (st!=c) {
            val=Move(par[st]);
            st=par[st];
        }
        return dfs1(c,-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:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs0(int, int, int)':
Joi.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Joi.cpp: In function 'void dfs1(int, int)':
Joi.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~

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

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1288 KB Output is correct
2 Correct 2 ms 1288 KB Output is correct
3 Correct 2 ms 1240 KB Output is correct
4 Incorrect 2 ms 1296 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 3400 KB Output is correct
2 Incorrect 28 ms 3380 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 1 ms 1288 KB Output is correct
4 Correct 3 ms 1820 KB Output is correct
5 Correct 4 ms 1824 KB Output is correct
6 Correct 2 ms 1824 KB Output is correct
7 Correct 3 ms 1820 KB Output is correct
8 Correct 2 ms 1692 KB Output is correct
9 Correct 11 ms 4172 KB Output is correct
10 Correct 13 ms 4164 KB Output is correct
11 Correct 16 ms 4152 KB Output is correct
12 Correct 2 ms 1284 KB Output is correct
13 Correct 1 ms 1288 KB Output is correct
14 Correct 1 ms 1284 KB Output is correct
15 Correct 2 ms 1280 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3356 KB Output is correct
2 Correct 22 ms 3356 KB Output is correct
3 Correct 25 ms 3436 KB Output is correct
4 Partially correct 16 ms 2884 KB Partially correct
5 Incorrect 14 ms 4032 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3356 KB Output is correct
2 Correct 26 ms 3328 KB Output is correct
3 Correct 24 ms 3404 KB Output is correct
4 Incorrect 13 ms 2884 KB Output isn't correct
5 Halted 0 ms 0 KB -