Submission #555715

#	Time	Username	Problem	Language	Result	Execution time	Memory
555715		Koosha_mv	Reconstruction Project (JOI22_reconstruction)	C++14	70 / 100	5062 ms	22688 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) ((int)x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

typedef pair<int,pair<int,int>> shit;

const int maxn=505,maxm=1e5+99,inf=2e9;

int n,m,q,L[maxm],R[maxm];
pair<int,int> par[maxn];
vector<shit> a,b;
vector<pair<int,int>> g[maxn];

void dfs(int u,int p){
	for(auto [v,w] : g[u]){
		if(v==p) continue ;
		dfs(v,u);
		par[v]={u,w};
	}
}
vector<int> solve(vector<shit> vec){
	f(i,1,n+1) g[i].clear();
	vector<int> ans;
	int i=0;
	for(auto [w,edge] : vec){
		fill(par,par+maxn,mp(0,0));
		dfs(edge.F,0);
		if(par[edge.S].F){
			int u=0,v=0,mn=sz(vec);
			for(int x=edge.S;x!=edge.F;x=par[x].F){
				if(par[x].S<mn){
					u=x,v=par[x].F;
					mn=par[x].S;;
				}
			}
			f(i,0,g[u].size()) if(g[u][i].F==v){
				g[u].erase(g[u].begin()+i);
			}
			f(i,0,g[v].size()) if(g[v][i].F==u){
				g[v].erase(g[v].begin()+i);
			}
			ans.pb(mn);
		}
		else{
			ans.pb(-1);
		}
		g[edge.F].pb({edge.S,i});
		g[edge.S].pb({edge.F,i});
		i++;
	}
	return ans;
}
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	f(i,0,m){
		int u,v,w;
		cin>>u>>v>>w;
		a.pb({w,{u,v}});
		b.pb({-w,{u,v}});
	} cout<<endl;
	sort(all(a));
	sort(all(b));
	vector<int> A=solve(a),B=solve(b);
	reverse(all(B));
	f(i,0,B.size()) B[i]=m-B[i]-1;
	for(auto p : a){
	//	cout<<p.S.F<<" "<<p.S.S<<" "<<p.F<<endl;
	}
	//dbgv(A);
	//dbgv(B);
	f(i,0,m){
		if(A[i]==-1) L[i]=0;
		else L[i]=(a[i].F+a[A[i]].F)/2+1;
	}
	f(i,0,m){
		if(B[i]==m) R[i]=inf;
		else{
			R[i]=(a[B[i]].F+a[i].F)/2;
		}
	}
	//dbga(L,0,m);
	//dbga(R,0,m);
	cin>>q;
	f(i,0,q){
		int x,ans=0;
		cin>>x;
		f(j,0,m){
			if(L[j]<=x && x<=R[j]){
				ans+=abs(x-a[j].F);
			}
		}
		cout<<ans<<'\n';
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'void dfs(long long int, long long int)':
reconstruction.cpp:34:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |  for(auto [v,w] : g[u]){
      |           ^
reconstruction.cpp: In function 'std::vector<long long int> solve(std::vector<std::pair<long long int, std::pair<long long int, long long int> > >)':
reconstruction.cpp:44:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |  for(auto [w,edge] : vec){
      |           ^
reconstruction.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   55 |    f(i,0,g[u].size()) if(g[u][i].F==v){
      |      ~~~~~~~~~~~~~~~           
reconstruction.cpp:55:4: note: in expansion of macro 'f'
   55 |    f(i,0,g[u].size()) if(g[u][i].F==v){
      |    ^
reconstruction.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   58 |    f(i,0,g[v].size()) if(g[v][i].F==u){
      |      ~~~~~~~~~~~~~~~           
reconstruction.cpp:58:4: note: in expansion of macro 'f'
   58 |    f(i,0,g[v].size()) if(g[v][i].F==u){
      |    ^
reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:8:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   85 |  f(i,0,B.size()) B[i]=m-B[i]-1;
      |    ~~~~~~~~~~~~                
reconstruction.cpp:85:2: note: in expansion of macro 'f'
   85 |  f(i,0,B.size()) B[i]=m-B[i]-1;
      |  ^
reconstruction.cpp:86:11: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   86 |  for(auto p : a){
      |           ^

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 0 / 23