제출 #862667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862667		hjroh0315	Xylophone (JOI18_xylophone)	C++17	0 / 100	0 ms	344 KiB

xylophone

#include<bits/stdc++.h>
#include"xylophone.h"
using namespace std;
using ll=long long;
const ll inf=1e18;

void solve(int N)
{
    vector<ll>D1(N),D2(N),dist(N+1,inf);
    for(ll i=1;i<N;i++)D1[i]=query(i,i+1);
    for(ll i=2;i<N;i++)D2[i]=query(i-1,i+1);
    vector<array<ll,3>>edge;
    for(ll i=1;i<N;i++)edge.push_back(array{i,i+1,D1[i]});
    for(ll i=2;i<N;i++)if(D2[i]!=D1[i-1]+D1[i])edge.push_back(array{i-1,i+1,abs(D1[i]-D1[i-1])});
    dist[1]=0;
    for(ll t=0;t<N;t++)
    for(auto[u,v,w]:edge)
    {
        dist[v]=min(dist[v],dist[u]+w);
        dist[u]=min(dist[u],dist[v]+w);
    }
    ll mn=inf;
    for(ll i=1;i<=N;i++)mn=min(mn,dist[i]);
    for(ll i=1;i<=N;i++)dist[i]+=mn+1;
    mn=inf;
    ll mi=-1,mx=-inf,mxi=-1;
    for(ll i=1;i<=N;i++)
    {
        if(mn>dist[i]){mn=dist[i];mi=i;}
        if(mx<dist[i]){mx=dist[i];mxi=i;}
    }
    for(ll i=1;i<=N;i++)answer(i,mi>mxi ? dist[i]:N+1-dist[i]);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53