이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define i3 tuple<int,int,int>
#define i4 tuple<int,int,int,int>
#define fi first
#define se second
//#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m,l,q;
struct E{ int to,w,id; };
vector<E> al[2005];
vector<ii> w[2005]; //ok so we store the best 2 guys...
priority_queue<i4,vector<i4>,greater<i4> > pq;
void add(int i,ii val){
if (w[i][0]==val || w[i][1]==val) return; //prevent from inserting dupes
//cout<<i<<" "<<val.fi<<" "<<val.se<<endl;
//rep(x,0,2) cout<<w[i][x].fi<<" "<<w[i][x].se<<endl;
if (val.fi<w[i][0].fi){
if (val.fi!=w[i][0].fi){
swap(w[i][0],w[i][1]);
pq.push({w[i][1].fi,w[i][1].se,i,1});
}
w[i][0]=val;
pq.push({w[i][0].fi,w[i][0].se,i,0});
}
else if (val.fi<w[i][1].fi && w[i][0].se!=val.se){
w[i][1]=val;
pq.push({w[i][1].fi,w[i][1].se,i,1});
}
}
struct dat{
vector<i3> res;
dat(){};
dat (vector<i3> temp){ //pick best 5
map<int,int> m1,m2;
set<ii> s;
sort(all(temp));
for (auto [w,a,b]:temp){
if (m1[a]==2 || m2[b]==2 || s.count({a,b})) continue;
m1[a]++,m2[b]++;
s.insert({a,b});
res.pub({w,a,b});
if (sz(res)==5) break;
}
}
};
dat merge(dat i,dat j){
vector<i3> temp;
for (auto [w,id1,id2]:i.res) for (auto [w2,id3,id4]:j.res){
if (id2!=id3) temp.pub({w+w2,id1,id4});
}
return dat(temp);
}
vector<i3> v[2005];
dat trans[2005][2005];
int arr[100005];
struct node{
int s,e,m;
dat val;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
val=merge(l->val,r->val);
}
else{
val=trans[arr[s]][arr[s+1]];
}
}
void update(int i){
if (s==e) val=trans[arr[i]][arr[i+1]];
else{
if (i<=m) l->update(i);
else r->update(i);
val=merge(l->val,r->val);
}
}
} *root;
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>m>>q>>l;
int a,b,c;
rep(x,0,m){
cin>>a>>b>>c;
al[a].pub({b,c,x});
al[b].pub({a,c,x});
}
rep(x,1,n+1){
rep(y,1,n+1) v[y].clear();
for (auto [y,_W,id]:al[x]){
rep(x,1,n+1){
w[x].clear();
rep(y,1,3) w[x].pub({1e18,-y});
}
add(y,{_W,id});
while (!pq.empty()){
int W,id,u,pos;
tie(W,id,u,pos)=pq.top(),pq.pop();
if (w[u][pos]!=ii(W,id)) continue;
for (auto [it,w2,id2]:al[u]) if (id!=id2){
add(it,{W+w2,id2});
}
}
rep(y,1,n+1) for (auto [w,id2]:w[y]) if (w<1e18){
v[y].pub({w,id,id2});
}
}
rep(y,1,n+1) trans[x][y]=dat(v[y]);
}
rep(x,1,l+1) cin>>arr[x];
root=new node(1,l-1);
while (q--){
cin>>a>>b;
arr[a]=b;
if (a!=1) root->update(a-1);
if (a!=l) root->update(a);
if (root->val.res.empty()) cout<<"-1"<<endl;
else cout<<get<0>(root->val.res[0])<<endl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
wild_boar.cpp: In constructor 'node::node(long long int, long long int)':
wild_boar.cpp:88:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | s=_s,e=_e,m=s+e>>1;
| ~^~
# | 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... |