oj.uz

답안 #566152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566152 2022-05-21T22:54:11 Z n0sk1ll 철로 (IOI14_rail) C++14
100 / 100
 102 ms 28000 KB 
#include "rail.h"
#include <bits/stdc++.h>

#define xx first
#define yy second

using namespace std;
long long int typedef li;

int dist[5003][5003];

int d(int i, int j)
{
    if (i>j) swap(i,j);
    if (!dist[i][j]) dist[i][j]=getDistance(i,j);
    return dist[i][j];
}

map<int,int> zauz;

void findLocation(int n, int first, int location[], int stype[])
{
    location[0]=first,stype[0]=1,zauz[first]=1;

    vector<pair<int,int>> ok;
    for (int i=1;i<n;i++) ok.push_back({d(0,i),i});
    sort(ok.begin(),ok.end());

    int L=0,R=ok.front().yy;
    location[R]=location[L]+d(L,R),stype[R]=2,zauz[location[R]]=stype[R];
    bool skip=true;

    for (auto [di,k] : ok)
    {
        if (skip)
        {
            skip=false;
            continue;
        }

        if (zauz[location[L]+(d(L,R)+d(L,k)-d(R,k))/2]==1) location[k]=location[L]+d(L,k),stype[k]=2;
        else if (zauz[location[R]-(d(L,R)+d(R,k)-d(L,k))/2]==2) location[k]=location[R]-d(R,k),stype[k]=1;
        else if (d(L,R)+d(0,k)-d(0,R)==d(L,k)) location[k]=location[L]+d(L,k),stype[k]=2;
        else location[k]=location[R]-d(R,k),stype[k]=1;

        zauz[location[k]]=stype[k];
        if (location[k]>location[R]) R=k;
        if (location[k]<location[L]) L=k;
    }
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for (auto [di,k] : ok)
      |               ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 22472 KB Output is correct
2 Correct 91 ms 24924 KB Output is correct
3 Correct 88 ms 26972 KB Output is correct
4 Correct 88 ms 27488 KB Output is correct
5 Correct 85 ms 21456 KB Output is correct
6 Correct 87 ms 18772 KB Output is correct
7 Correct 84 ms 22364 KB Output is correct
8 Correct 88 ms 28000 KB Output is correct
9 Correct 84 ms 26296 KB Output is correct
10 Correct 98 ms 25680 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 22484 KB Output is correct
2 Correct 88 ms 24932 KB Output is correct
3 Correct 96 ms 26956 KB Output is correct
4 Correct 88 ms 27468 KB Output is correct
5 Correct 82 ms 21468 KB Output is correct
6 Correct 87 ms 18764 KB Output is correct
7 Correct 89 ms 22364 KB Output is correct
8 Correct 94 ms 27984 KB Output is correct
9 Correct 89 ms 26228 KB Output is correct
10 Correct 82 ms 25688 KB Output is correct
11 Correct 84 ms 21600 KB Output is correct
12 Correct 96 ms 21712 KB Output is correct
13 Correct 91 ms 25440 KB Output is correct
14 Correct 80 ms 21720 KB Output is correct
15 Correct 84 ms 27340 KB Output is correct
16 Correct 84 ms 25164 KB Output is correct
17 Correct 102 ms 20436 KB Output is correct
18 Correct 87 ms 22348 KB Output is correct
19 Correct 83 ms 24912 KB Output is correct
20 Correct 79 ms 21840 KB Output is correct