QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#569983#5148. Tree DistanceaaaaaCompile Error//C++202.4kb2024-09-17 13:04:382024-09-17 13:04:39

Judging History

This is the latest submission verdict.

  • [2024-09-17 13:04:39]
  • Judged
  • [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);
      |                 ~~~~~^~~~~~~~~~~~~~