oj.uz

Submission #862667

# Submission time Handle Problem Language Result Execution time Memory
862667 2023-10-18T18:56:47 Z hjroh0315 Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -