C++11(clang++ 3.9) 解法, 执行用时: 4228ms, 内存消耗: 211536K, 提交时间: 2020-06-01 21:39:26
/*
可以用平衡树搞,
也可以用线段树二分加动态开点搞.
好像都很麻烦呢.
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,M=2e7+50;
const ll low=-5e14,up=5e14;
int n,m,q;
int rt,tot;
int siz,sum;
bool vis[N];
int t[M],ls[M],rs[M];
ll ans[N],dis[N],cf[N];
int b[N],head[N],nex[N<<1],to[N<<1],wi[N<<1];
vector<pair<int,int>>v[N];
int newnode() {
tot++;
t[tot]=ls[tot]=rs[tot]=0;
return tot;
}
void add(int u,int v,int w) {
to[++sum]=v;
nex[sum]=head[u];
head[u]=sum;
wi[sum]=w;
}
void Insert(ll l,ll r,ll x,int &now,int v) {
if(!now) now=newnode();
t[now]+=v;
if(l==r) return;
ll m=l+r>>1;
if(x<=m) Insert(l,m,x,ls[now],v);
else Insert(m+1,r,x,rs[now],v);
}
ll query(ll l,ll r,int k,int &now) {
if(l==r) return l;
ll m=l+r>>1;
if(t[rs[now]]>=k) return query(m+1,r,k,rs[now]);
return query(l,m,k-t[rs[now]],ls[now]);
}
void dfs1(int u) {
siz++;
assert(dis[u]>=low&&dis[u]<=up);
Insert(low,up,dis[u],rt,1);
vis[u]=true;
for(int i=head[u]; i; i=nex[i]) {
int v=to[i];
if(vis[v]) continue;
cf[v]=dis[v]=dis[u]+wi[i];
dfs1(v);
}
}
void updata(int u,int p,ll w) {
Insert(low,up,dis[u],rt,-1);
dis[u]+=w;
assert(dis[u]>=low&&dis[u]<=up);
Insert(low,up,dis[u],rt,1);
for(int i=head[u]; i; i=nex[i]) {
int v=to[i];
if(v==p) continue;
updata(v,u,w);
}
}
void dfs2(int u,int p) {
for(pair<int,int>x:v[u]) {
if(x.first>=siz) ans[x.second]=-1;
else ans[x.second]=query(low,up,x.first,rt)+cf[u];
}
for(int i=head[u]; i; i=nex[i]) {
int v=to[i];
if(v==p) continue;
updata(v,u,-2ll*wi[i]);
dfs2(v,u);
updata(v,u,2ll*wi[i]);
}
}
void solve(int x) {
rt=tot=siz=0;
dfs1(x);
dfs2(x,0);
}
int main() {
scanf("%d%d%d",&n,&m,&q);
// random_shuffle(b+1,b+1+n);
for(int i=1; i<=m; i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i=1; i<=q; i++) {
int x,k;
scanf("%d%d",&x,&k);
v[x].push_back({k,i});
}
for(int i=1; i<=n; i++)
if(!vis[i]) {
solve(i);
}
for(int i=1; i<=q; i++) printf("%lld\n",ans[i]);
}
C++14(g++5.4) 解法, 执行用时: 4508ms, 内存消耗: 407288K, 提交时间: 2020-04-30 10:43:21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
const ll low=-1e15,up=1e15;
ll rt,tot,t[N*100],ls[N*100],rs[N*100];
ll newnode(){tot++;t[tot]=ls[tot]=rs[tot]=0;return tot;}
ll ans[N],dis[N],cf[N];
bool vis[N];
ll n,m,q,si,sum,head[N],nex[N<<1],to[N<<1],wi[N<<1];
void add(ll u,ll v,ll w){to[++sum]=v;nex[sum]=head[u];head[u]=sum;wi[sum]=w;}
vector<pair<ll,ll>>v[N];
void Insert(ll l,ll r,ll x,ll &now,ll v)
{
if(!now) now=newnode();
t[now]+=v;
if(l==r) return;
ll m=l+r>>1;
if(x<=m) Insert(l,m,x,ls[now],v);
else Insert(m+1,r,x,rs[now],v);
}
ll query(ll l,ll r,ll k,ll &now)
{
if(l==r) return l;
ll m=l+r>>1;
if(t[rs[now]]>=k) return query(m+1,r,k,rs[now]);
return query(l,m,k-t[rs[now]],ls[now]);
}
void dfs(ll u)
{
si++;
Insert(low,up,dis[u],rt,1);
vis[u]=true;
for(ll i=head[u];i;i=nex[i])
{
ll v=to[i];if(vis[v])continue;
cf[v]=dis[v]=dis[u]+wi[i];
dfs(v);
}
}
void vvv(ll u,ll p,ll w)
{
Insert(low,up,dis[u],rt,-1);
dis[u]+=w;
Insert(low,up,dis[u],rt,1);
for(ll i=head[u];i;i=nex[i])
{
ll v=to[i];if(v==p) continue;
vvv(v,u,w);
}
}
void dfs(ll u,ll p)
{
for(pair<ll,ll>x:v[u])
{
if(x.first>=si) ans[x.second]=-1;
else ans[x.second]=query(low,up,x.first,rt)+cf[u];
}
for(ll i=head[u];i;i=nex[i])
{
ll v=to[i];if(v==p) continue;
vvv(v,u,-2ll*wi[i]);
dfs(v,u);
vvv(v,u,2ll*wi[i]);
}
}
void solve(ll x)
{
rt=tot=si=0;
dfs(x);
dfs(x,0);
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(ll i=1;i<=m;i++)
{
ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
for(ll i=1;i<=q;i++)
{
ll x,k;scanf("%lld%lld",&x,&k);
v[x].push_back({k,i});
}
for(ll i=1;i<=n;i++)
if(!vis[i])
{
solve(i);
}
for(ll i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
