oj.uz

Submission #590637

# Submission time Handle Problem Language Result Execution time Memory
590637 2022-07-06T07:54:24 Z 조영욱(#8414) Amusement Park (JOI17_amusement_park) C++14
10 / 100
 26 ms 4012 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;
        }
        //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]);
        }
    }
    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];
int ind[10000];
int rev[10000];
int sz[10000];
int md[10000];
int f=0;

void dfs(int v,int prev) {
    par[v]=prev;
    md[v]=dep[v];
    sz[v]=1;
    ind[v]=f++;
    rev[ind[v]]=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]);
            sz[v]+=sz[nt];
        }
    }
}

bool need[10000];
long long chk[60];

void dfs1(int v,int prev) {
    chk[ind[v]%60]=val;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev||!need[nt]) {
            continue;
        }
        val=Move(nt);
        dfs1(nt,v);
        val=Move(v);
    }
}

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]);
        }
    }
    dfs(0,-1);
    int now=st;
    int pr=-1;
    while (sz[now]<60) {
        pr=now;
        now=par[now];
    }
    need[now]=true;
    int l=ind[now];
    int r=ind[now]+sz[now]-1;
    int vst=0;
    if (pr==-1) {
        vst=l;
    }
    else {
        int ll=ind[pr];
        int rr=ind[pr]+sz[pr]-1;
        while (rr-ll<59) {
            if (ll!=l) {
                ll--;
            }
            else if (rr!=r) {
                rr++;
            }
        }
        vst=ll;
    }
    for(int i=vst;i<vst+60;i++) {
        need[rev[i]]=true;
    }
    dfs1(st,-1);
    long long ret=0;
    for(int i=0;i<60;i++) {
        ret+=(chk[i]<<i);
    }
    return ret;
}

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:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     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:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs1(int, int)':
Ioi.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~

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 Correct 22 ms 3352 KB Output is correct
2 Incorrect 23 ms 3288 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 2 ms 1288 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 2 ms 1696 KB Output is correct
5 Correct 3 ms 1700 KB Output is correct
6 Correct 2 ms 1700 KB Output is correct
7 Correct 3 ms 1700 KB Output is correct
8 Correct 2 ms 1696 KB Output is correct
9 Correct 15 ms 3932 KB Output is correct
10 Correct 11 ms 4012 KB Output is correct
11 Correct 15 ms 3972 KB Output is correct
12 Correct 2 ms 1288 KB Output is correct
13 Correct 1 ms 1280 KB Output is correct
14 Correct 0 ms 1280 KB Output is correct
15 Correct 1 ms 1280 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3316 KB Output is correct
2 Incorrect 20 ms 3416 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3420 KB Output is correct
2 Incorrect 26 ms 3840 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -