Submission #74540441

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long 

const int N=3000+5;

bool st;
int n;
int a[N][N],f[N];
struct node{int id,num,dep;}x[N];
bool cmp(node a,node b) {
	if(a.num!=b.num) return a.num<b.num;
	return a.id<b.id;
}
struct edge{int u,v,w;};
vector<edge> g[N];
int fa[N][20],dis[N],dep[N];
inline int lca(int u,int v) {
	if(dis[u]<dis[v]) swap(u,v);
	if(dis[u]!=dis[v]) {
		for(int i=12;i>=0;i--) {
			if(dis[fa[u][i]]>=dis[v]) u=fa[u][i];
		}
	}
	if(u==v) return u;
	for(int i=12;i>=0;i--) {
		if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	}return fa[u][0];
}
inline void dfs(int u) {
	fa[u][0]=f[u];
	for(int i=1;i<=12;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i].v;
		if(v==f[u]) continue;
		dep[v]=dep[u]+g[u][i].w;
		dfs(v);
	}
}
bool ed;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cerr<<(double)(&st-&ed)/1024/1024<<'\n';
	cin>>n;
	for(int i=1;i<=n;i++) {
		for(int j=i+1;j<=n;j++) {
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++) x[i].id=i,x[i].num=a[1][i];
	sort(x+1,x+n+1,cmp);
	for(int i=2;i<=n;i++) {
		int maxn=-1,maxid=0,u=x[i].id;
		for(int j=i-1;j>=1;j--) {
			int v=x[j].id;
			if(a[1][u]!=a[1][v]+a[min(u,v)][max(u,v)]) continue;
			if(dis[v]>maxn) maxn=dis[v],maxid=v; 
		}
		int w=a[min(u,maxid)][max(u,maxid)];
		f[u]=maxid,dis[u]=dis[maxid]+1;
		g[u].push_back({u,maxid,w});
		g[maxid].push_back({maxid,u,w});
	}
	dfs(1);
	for(int i=1;i<=n;i++) {
		for(int j=i+1;j<=n;j++) {
			int s=lca(i,j);
			if(dep[i]+dep[j]-2*dep[s]!=a[i][j])  {
				cout<<"No"<<'\n';
				return 0;
			}
		}
	}cout<<"Yes\n";
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'void dfs(long long int)':
./Main.cpp:34:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i=0;i<g[u].size();i++) {
      |                     ~^~~~~~~~~~~~

Judge Result