Submission #1104280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104280		overwatch9	Lost Array (NOI19_lostarray)	C++17	100 / 100	206 ms	15432 KiB

lostarray

#include <bits/stdc++.h>
using namespace std;
bool comp(array <int, 3> a, array <int, 3> b) {
    return a[2] < b[2];
}
int main() {
    int n, m;
    cin >> n >> m;
    map <int, multiset <int>> mp;
    vector <array <int, 3>> nums(m);
    for (int i = 0; i < m; i++) {
        cin >> nums[i][0] >> nums[i][1] >> nums[i][2];
        mp[nums[i][0]].insert(nums[i][2]);
        mp[nums[i][1]].insert(nums[i][2]);
    }
    vector <int> ans(n+1, 1e9);
    sort(nums.begin(), nums.end(), comp);
    for (int i = 0; i < m; i++) {
        int a = nums[i][0], b = nums[i][1], c = nums[i][2];
        if (*mp[a].begin() == c)
            ans[a] = c;
        if (*mp[b].begin() == c)
            ans[b] = c;
        mp[a].erase(mp[a].find(c));
        mp[b].erase(mp[b].find(c));
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    cout << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 48 / 48