oj.uz

답안 #566151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566151 2022-05-21T22:53:46 Z n0sk1ll 철로 (IOI14_rail) C++14
100 / 100
 102 ms 28060 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;
    }
}

/*

4
4
1 1
1 2
2 5
2 6

*/

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 1 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 85 ms 22488 KB Output is correct
2 Correct 93 ms 24952 KB Output is correct
3 Correct 91 ms 27000 KB Output is correct
4 Correct 84 ms 27568 KB Output is correct
5 Correct 86 ms 21508 KB Output is correct
6 Correct 102 ms 18808 KB Output is correct
7 Correct 83 ms 22408 KB Output is correct
8 Correct 87 ms 28060 KB Output is correct
9 Correct 86 ms 26236 KB Output is correct
10 Correct 92 ms 25728 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 22476 KB Output is correct
2 Correct 82 ms 24956 KB Output is correct
3 Correct 99 ms 27132 KB Output is correct
4 Correct 91 ms 27524 KB Output is correct
5 Correct 85 ms 21500 KB Output is correct
6 Correct 84 ms 18824 KB Output is correct
7 Correct 81 ms 22412 KB Output is correct
8 Correct 98 ms 28040 KB Output is correct
9 Correct 91 ms 26232 KB Output is correct
10 Correct 84 ms 25804 KB Output is correct
11 Correct 84 ms 21628 KB Output is correct
12 Correct 86 ms 21756 KB Output is correct
13 Correct 97 ms 25468 KB Output is correct
14 Correct 80 ms 21836 KB Output is correct
15 Correct 84 ms 27388 KB Output is correct
16 Correct 93 ms 25224 KB Output is correct
17 Correct 97 ms 20472 KB Output is correct
18 Correct 80 ms 22396 KB Output is correct
19 Correct 86 ms 24968 KB Output is correct
20 Correct 88 ms 21900 KB Output is correct