이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
ID: blackha5
TASK: test
LANG: C++
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ff first
#define ss second
#define Maxn 100003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;
bool vis[Maxn];
bool vis1[Maxn];
int p[Maxn];
int ans[Maxn];
int dis[Maxn];
int a[Maxn * 5];
int b[Maxn * 5];
int n, m, k, g, Q;
int L[Maxn], R[Maxn];
set <pair <int, pii> > s;
vector <pii> adj[Maxn];
priority_queue <pii, vector <pii>, greater <pii> > q;
void dij () {
while (!q.empty()) {
pii x = q.top();
q.pop();
if (vis[x.ss])
continue;
vis[x.ss] = 1;
for (auto i: adj[x.ss]) {
dis[i.ff] = min (dis[i.ff], x.ff + i.ss);
q.push ({dis[i.ff], i.ff});
}
}
}
int dsu (int x) {
while (p[x] == x)
return x;
return p[x] = dsu (p[x]);
}
void dfs (int nd, int x) {
if (vis1[nd])
return;
vis1[nd] = 1;
for (auto i: adj[nd]) {
if (!vis1[i.ff]) {
if (x > dis[i.ff])
s.insert ({dis[i.ff], {nd, i.ff}});
else {
s.erase ({dis[i.ff], {nd, i.ff}});
p[dsu (nd)] = dsu (i.ff);
dfs (i.ff, x);
}
}
else {
if (x <= dis[i.ff])
p[dsu (nd)] = dsu (i.ff);
else
s.insert ({dis[i.ff], {nd, i.ff}});
}
}
}
int main () {
//freopen ("file.in", "r", stdin);
//freopen ("file.out", "w", stdout);
//srand ((unsigned) time ( NULL ));
//int randomNumber = rand() % 10 + 1;
scanf ("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf ("%d%d%d", &u, &v, &w);
adj[u].pb ({v, w});
adj[v].pb ({u, w});
}
for (int i = 1; i <= n; i++)
dis[i] = Inf, p[i] = i;
scanf ("%d", &k);
for (int i = 1; i <= k; i++)
scanf ("%d", &g), dis[g] = 0, q.push ({0, g});
dij();
scanf ("%d", &Q);
for (int i = 1; i <= Q; i++) {
scanf ("%d%d", &a[i], &b[i]);
L[i] = 0;
R[i] = 1e9;
}
while (1) {
s.clear();
memset (vis1, 0, sizeof (vis1));
for (int i = 1; i <= n; i++)
p[i] = i;
vector <pii> v;
for (int i = 1; i <= Q; i++) {
if (L[i] <= R[i])
v.pb ({mid (L[i], R[i]), i});
}
if (!v.size())
break;
sort (all(v));
reverse (all(v));
for (auto i: v) {
while (1) {
if (s.size() > 0) {
pair <int, pii> d = *s.rbegin();
if (i.ff <= d.ff) {
s.erase (d);
p[dsu(d.ss.ff)] = dsu (d.ss.ss);
dfs (d.ss.ss, i.ff);
}
else
break;
}
else
break;
}
if (!vis1[a[i.ss]] and i.ff <= dis[a[i.ss]])
dfs (a[i.ss], i.ff);
if (p[dsu(a[i.ss])] == p[dsu(b[i.ss])])
ans[i.ss] = i.ff, L[i.ss] = i.ff + 1;
else
R[i.ss] = i.ff - 1;
}
}
for (int i = 1; i <= Q; i++)
printf ("%d\n", ans[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp: In function 'int main()':
plan.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &n, &m);
~~~~~~^~~~~~~~~~~~~~~~
plan.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &u, &v, &w);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &k);
~~~~~~^~~~~~~~~~
plan.cpp:112:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &g), dis[g] = 0, q.push ({0, g});
~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &Q);
~~~~~~^~~~~~~~~~
plan.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &a[i], &b[i]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |