# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672834 | sugartheanh | Aesthetic (NOI20_aesthetic) | C++14 | 608 ms | 41528 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long r[2][300000];
bool vt[300000], f[300000];
int A[300000][4], p[300000], q[300000], d[300000], id[300000];
vector<pair<pair<int, int>, int> > adj[300000];
priority_queue<pair<pair<long long, int>, pair<int, int> > > pq;
int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);}
void it(int i, int t, int o, int l, long long v) {
if (vt[i]) return;
vt[i] = 1;
if (!t) {p[i] = o; q[i] = l; d[i] = d[o] + !!i;}
r[t][i] = v;
for (int j = 0; j < adj[i].size(); ++j) if (!vt[adj[i][j].first.first]) pq.emplace(make_pair(-v - adj[i][j].first.second, adj[i][j].first.first), make_pair(i, adj[i][j].second));
}
int main() {
//freopen("in.txt", "r", stdin);
int N, M, a, b, x, i, j;
long long l, h, c;
bool e;
scanf("%d %d", &N, &M);
for (i = 0; i < M; ++i) {for (j = 0; j < 3; ++j) scanf("%d", &A[i][j]); adj[--A[i][0]].emplace_back(make_pair(--A[i][1], A[i][2]), i); adj[A[i][1]].emplace_back(make_pair(A[i][0], A[i][2]), i);}
for (i = M - 2; i > -1; --i) A[i][3] = max(A[i + 1][2], A[i + 1][3]);
it(0, 0, 0, -1, 0);
while (!pq.empty()) x = pq.top().first.second, c = -pq.top().first.first, a = pq.top().second.first, b = pq.top().second.second, pq.pop(), it(x, 0, a, b, c);
memset(vt, 0, sizeof(vt));
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |