oj.uz

답안 #415657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415657 2021-06-01T10:37:18 Z 최서현(#7480) Road Construction (JOI21_road_construction) C++17
6 / 100
 596 ms 25108 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;
    sort(A, A + n);
    int B[n - 1]; for(int i = 0; i < n - 1; ++i) B[i] = A[i + 1].ff - A[i].ff;

    priority_queue<piii, vector<piii>, greater<piii>> Q;
    set<pii> S;
    for(int i = 0; i < n - 1; ++i) Q.push({A[i + 1].ff - A[i].ff, {i, i + 1}});
    while(k--)
    {
        auto x = Q.top(); Q.pop();
        if(S.count(x.ss)) {k++; continue;}
        S.insert(x.ss);
        cout << x.ff << '\n';
        if(x.ee != 0) Q.push({A[x.rr].ff - A[x.ee - 1].ff, {x.ee - 1, x.rr}});
        if(x.rr != n - 1) Q.push({A[x.rr + 1].ff - A[x.ee].ff, {x.ee, x.rr + 1}});
    }
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:30:9: warning: variable 'B' set but not used [-Wunused-but-set-variable]
   30 |     int B[n - 1]; for(int i = 0; i < n - 1; ++i) B[i] = A[i + 1].ff - A[i].ff;
      |         ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 301 ms 14688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 23972 KB Output is correct
2 Correct 596 ms 23988 KB Output is correct
3 Correct 271 ms 14524 KB Output is correct
4 Correct 401 ms 21932 KB Output is correct
5 Correct 253 ms 24976 KB Output is correct
6 Correct 241 ms 25108 KB Output is correct
7 Correct 265 ms 23628 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 120 ms 11544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 120 ms 11544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 301 ms 14688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 301 ms 14688 KB Output isn't correct
2 Halted 0 ms 0 KB -