QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#569983 | #5148. Tree Distance | aaaaa | Compile Error | / | / | C++20 | 2.4kb | 2024-09-17 13:04:38 | 2024-09-17 13:04:39 |
Judging History
This is the latest submission verdict.
- [2024-09-17 13:04:39]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-09-17 13:04:38]
- Submitted
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=300010,M=1000010;
ll n,tot,first[N],nnext[N<<1],to[N<<1],w[N<<1],siz[N],f[N],root,s,a[N],cnt,vis[N],cntd;
ll dis[N],pp[N],ans[M];
unordered_set<ll>ss;
// vector<pair<ll,ll> >p[N];
unordered_map<ll, vector<pair<ll, ll>>> p;
struct sss {
ll x,y;
ll v;
bool operator<(sss b) {
return x<b.x;
}
} d[M*7];
void add(ll x,ll y,ll z) {
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
}
void getroot(ll u,ll fa) {
siz[u]=1;
f[u]=0;
for(ll e=first[u]; e; e=nnext[e]) {
if(!vis[to[e]]&&to[e]!=fa) {
getroot(to[e],u);
siz[u]+=siz[to[e]];
f[u]=max(f[u],siz[to[e]]);
}
}
f[u]=max(f[u],s-siz[u]);
if(f[u]<f[root]) {
root=u;
}
}
void getdep(ll u,ll fa) {
a[++cnt]=u;
for(ll e=first[u]; e; e=nnext[e]) {
if(!vis[to[e]]&&to[e]!=fa) {
dis[to[e]]=dis[u]+w[e];
getdep(to[e],u);
}
}
}
void dfs(ll u) {
dis[u]=cnt=0;
vis[u]=1;
getdep(u,0);
sort(a+1,a+cnt+1,[](ll a,ll b) {
return dis[a]<dis[b];
});
ss.clear();
for(ll i=1; i<=cnt; i++) {
ss.insert(a[i]);
auto pos=ss.find(a[i]);
if(pos!=ss.begin()) {
pos--;
d[++cntd]= {*pos,a[i],dis[*pos]+dis[a[i]]};
pos++;
}
pos++;
if(pos!=ss.end()) {
d[++cntd]= {*pos,a[i],dis[*pos]+dis[a[i]]};
}
}
for(ll e=first[u]; e; e=nnext[e]) {
if(!vis[to[e]]) {
root=0;
s=siz[to[e]];
getroot(to[e],u);
dfs(root);
}
}
}
inline ll lowbit(ll x) {
return x&(-x);
}
inline void update(ll x,ll y) {
while(x<=n) {
pp[x]=min(pp[x],y);
x+=lowbit(x);
}
}
inline ll query(ll x) {
ll ans=1e18;
while(x>=1) {
ans=min(ans,pp[x]);
x-=lowbit(x);
}
return ans;
}
int main() {
ll now,a,b,c,q;
scanf("%d",&n);
for(ll i=1; i<=n-1; i++) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
f[0]=1e18;
s=n;
getroot(1,0);
dfs(root);
for(ll i=1; i<=cntd; i++) {
if(d[i].x>d[i].y) {
swap(d[i].x,d[i].y);
}
}
sort(d+1,d+cntd+1);
now=cntd;
scanf("%d",&q);
for(ll i=1; i<=q; i++) {
scanf("%d%d",&a,&b);
if(a>=b) {
ans[i]=-1;
continue;
}
p[a].push_back({b,i});
}
memset(pp,127,sizeof(pp));
for(ll i=n; i>=1; i--) {
while(d[now].x>=i) {
update(d[now].y,d[now].v);
now--;
}
for(auto j:p[i]) {
ans[j.second]=query(j.first);
}
}
for(ll i=1; i<=q; i++) {
prllf("%lld\n",ans[i]);
}
}
详细
answer.code: In function ‘void dfs(long long int)’: answer.code:59:28: error: no ‘operator--(int)’ declared for postfix ‘--’ [-fpermissive] 59 | pos--; | ~~~^~ answer.code: In function ‘int main()’: answer.code:96:17: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=] 96 | scanf("%d",&n); | ~^ ~~ | | | | | long long int* | int* | %lld answer.code:98:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=] 98 | scanf("%d%d%d",&a,&b,&c); | ~^ ~~ | | | | int* long long int* | %lld answer.code:98:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘long long int*’ [-Wformat=] 98 | scanf("%d%d%d",&a,&b,&c); | ~^ ~~ | | | | int* long long int* | %lld answer.code:98:29: warning: format ‘%d’ expects argument of type ‘int*’, but argument 4 has type ‘long long int*’ [-Wformat=] 98 | scanf("%d%d%d",&a,&b,&c); | ~^ ~~ | | | | int* long long int* | %lld answer.code:113:17: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=] 113 | scanf("%d",&q); | ~^ ~~ | | | | | long long int* | int* | %lld answer.code:115:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=] 115 | scanf("%d%d",&a,&b); | ~^ ~~ | | | | int* long long int* | %lld answer.code:115:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘long long int*’ [-Wformat=] 115 | scanf("%d%d",&a,&b); | ~^ ~~ | | | | int* long long int* | %lld answer.code:133:17: error: ‘prllf’ was not declared in this scope 133 | prllf("%lld\n",ans[i]); | ^~~~~ answer.code:96:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 96 | scanf("%d",&n); | ~~~~~^~~~~~~~~ answer.code:98:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 98 | scanf("%d%d%d",&a,&b,&c); | ~~~~~^~~~~~~~~~~~~~~~~~~ answer.code:113:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 113 | scanf("%d",&q); | ~~~~~^~~~~~~~~ answer.code:115:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 115 | scanf("%d%d",&a,&b); | ~~~~~^~~~~~~~~~~~~~