QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#819480#9733. Heavy-light DecompositionTosakaUCW#WA 1ms3752kbC++201.4kb2024-12-18 15:54:332024-12-18 15:54:34

Judging History

This is the latest submission verdict.

  • [2024-12-18 15:54:34]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3752kb
  • [2024-12-18 15:54:33]
  • Submitted

answer

#include <bits/stdc++.h>

#define int long long

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::endl;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> l(k), r(k);
    for(int i = 0;i < k; i++) {
        cin >> l[i] >> r[i];
    }

    vector<int> p(k);
    std::iota(p.begin(), p.end(), 0LL);

    std::sort(p.begin(), p.end(), [&](int i, int j) {
        if(r[i] - l[i] == r[j] - l[j]) {
            return i < j;
        }
        return (r[i] - l[i]) > (r[j] - l[j]);
    });

    auto seg = [&](int i) {
        return r[i] - l[i];
    };

    if(seg(p[0]) == seg(p[1])) {
        cout << "IMPOSSIBLE\n";
        return;
    }

    vector<int> ans(n + 1);
    int root = -1;

    for(int j = 0;j < k; j++) {
        int i = p[j];
        if(j == 0) {
            ans[l[i]] = 0;
            root = l[i];
            for(int k = l[i] + 1;k <= r[i]; k++) {
                ans[k] = k - 1;
            }
        }else {
            ans[l[i]] = root;
            for(int k = l[i] + 1;k <= r[i]; k++) {
                ans[k] = k - 1;
            }
        }
    }

    for(int i = 1;i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int T;
    cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3512kb

input:

3
12 5
1 5
9 11
7 8
6 6
12 12
4 3
1 1
4 4
2 3
2 2
1 1
2 2

output:

0 1 2 3 4 1 1 7 1 9 10 1 
2 0 2 2 
IMPOSSIBLE

result:

ok Correct. (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3752kb

input:

10
1 1
1 1
100000 1
1 100000
12 4
1 3
4 6
7 9
10 12
6 3
4 6
2 3
1 1
8999 3
1 3000
3001 6000
6001 8999
14 4
1 3
4 6
7 10
11 14
17 5
1 3
4 6
7 10
11 14
15 17
19999 2
1 9999
10000 19999
1 1
1 1
5 3
1 1
2 3
4 5

output:

IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
4 4 2 0 4 5 
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
10000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75...

result:

wrong answer Case 1, jury find a solution while participant not. (test case 1)