이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;
class dsu {
public:
int uparent[maxn], n;
int usize[maxn];
void init(int _n) {
n = _n;
for(int i=0;i<=n;i++) {
uparent[i] = i;
usize[i] = 1;
}
}
int ufind(int x) {
while(x != uparent[x])
x = uparent[x];
return x;
}
void unite(int x, int y) {
x = ufind(x);
y = ufind(y);
if(x == y) return;
if(usize[x] > usize[y]) {
uparent[y] = x;
usize[x] += usize[y];
}
else {
uparent[x] = y;
usize[y] += usize[x];
}
}
}D;
int n, m, k, q, sz;
int result[maxn];
int dist[maxn];
bool visited[maxn];
vector<int>v; // NPP indexes
vector<pair<int,int> > g[maxn];
void get_distances() {
for(int i=0;i<=n;i++) {
visited[i] = false;
dist[i] = INT_MAX;
}
priority_queue<pii, vector<pii>, greater<pii> > pq;
for(int i:v) {
dist[i] = 0;
pq.push(mp(0, i));
}
while(!pq.empty()) {
int node = pq.top().second;
int curr = pq.top().first;
pq.pop();
if(visited[node]) continue;
visited[node] = true;
for(auto i:g[node]) {
if(!visited[i.first] && dist[i.first] > curr + i.second) {
dist[i.first] = curr + i.second;
pq.push(mp(dist[i.first], i.first));
}
}
}
}
int orgval[maxn];
vector<int>indexes[maxn];
map<int, int>cind;
set<int>st;
void preprocess() {
for(int i=1;i<=n;i++) {
st.insert(dist[i]);
}
int br = 0;
for(int i:st) {
cind[i] = br;
orgval[br] = i;
br++;
}
sz = br;
for(int i=1;i<=n;i++) {
indexes[cind[dist[i]]].pb(i);
}
}
int ql[maxn], qr[maxn];
int qs[maxn], qt[maxn];
bool answ[maxn];
int main() {
cin>>n>>m;
int a, b, c;
for(int i=0;i<m;i++) {
cin>>a>>b>>c;
g[a].pb(mp(b, c));
g[b].pb(mp(a, c));
}
int x;
cin>>k;
for(int i=0;i<k;i++) {
cin>>x;
v.pb(x);
}
get_distances();
preprocess();
cin>>q;
for(int i=1;i<=q;i++) {
cin>>qs[i]>>qt[i];
ql[i] = -1, qr[i] = sz;
}
for(int d=0;d<20;d++) {
//cout<<"At level: "<<d<<"\n";
D.init(n);
vector<int>qrs[maxn];
memset(answ,false,sizeof(answ));
//cout<<"Queries at beginning\n";
for(int i=1;i<=q;i++) {
int mid = (ql[i] + qr[i]) / 2;
if(qr[i] - ql[i] <= 1) {
result[i] = orgval[ql[i]];
continue;
}
qrs[mid].pb(i);
}
for(int j=sz-1;j>=0;j--) {
for(int i:indexes[j]) {
for(auto nxt:g[i]) {
if(dist[i] <= dist[nxt.first]) {
D.unite(i, nxt.first);
}
}
}
for(int i:qrs[j]) {
if(D.ufind(qs[i]) == D.ufind(qt[i])) {
answ[i] = true;
}
}
}
for(int i=1;i<=q;i++) {
if(qr[i] - ql[i] <= 1) continue;
int mid = (ql[i] + qr[i]) / 2;
if(answ[i]) {
ql[i] = mid;
}
else {
qr[i] = mid;
}
}
}
for(int i=1;i<=q;i++) {
cout<<result[i]<<"\n";
}
}
# | 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... |