Submission #555735

#	Time	Username	Problem	Language	Result	Execution time	Memory
555735		Koosha_mv	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2971 ms	42724 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],fenwik[2][maxm];
pair<int,int> par[maxn];
vector<shit> a,b;
vector<pair<int,int>> g[maxn];

void add(int x, int val,int s){ for(x++;x<maxm;x+=x&-x) fenwik[s][x]+=val; }
int get(int x,int s) { int res=0; for (x++;x>0;x-=x&-x) res+=fenwik[s][x]; return res; }

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}});
	}
	sort(all(a));
	sort(all(b));
	vector<int> A=solve(a),B=solve(b);
	vector<shit> vec;
	reverse(all(B));
	f(i,0,B.size()) B[i]=m-B[i]-1;
	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+1;
		}
		vec.pb({L[i],{i,+1}});
		vec.pb({R[i],{i,-1}});
	}
	int sum=0,cnt=0,p=0;
	sort(all(vec));
	cin>>q;
	f(i,0,q){
		int x;
		cin>>x;
		while(p<vec.size() && vec[p].F<=x){
			add(vec[p].S.F,vec[p].S.S,0);
			add(vec[p].S.F,vec[p].S.S*a[vec[p].S.F].F,1);
			p++;
		}
		int l=-1,r=m;
		while(l+1<r){
			int mid=(l+r)>>1;
			if(a[mid].F<=x) l=mid;
			else r=mid;
		}
		cout<<get(l,0)*x-get(l,1)+(get(m,1)-get(l,1))-x*(get(m,0)-get(l,0))<<'\n';
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'void dfs(long long int, long long int)':
reconstruction.cpp:37:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |  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:47:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  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++)
......
   58 |    f(i,0,g[u].size()) if(g[u][i].F==v){
      |      ~~~~~~~~~~~~~~~           
reconstruction.cpp:58:4: note: in expansion of macro 'f'
   58 |    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++)
......
   61 |    f(i,0,g[v].size()) if(g[v][i].F==u){
      |      ~~~~~~~~~~~~~~~           
reconstruction.cpp:61:4: note: in expansion of macro 'f'
   61 |    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++)
......
   89 |  f(i,0,B.size()) B[i]=m-B[i]-1;
      |    ~~~~~~~~~~~~                
reconstruction.cpp:89:2: note: in expansion of macro 'f'
   89 |  f(i,0,B.size()) B[i]=m-B[i]-1;
      |  ^
reconstruction.cpp:108:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   while(p<vec.size() && vec[p].F<=x){
      |         ~^~~~~~~~~~~
reconstruction.cpp:102:6: warning: unused variable 'sum' [-Wunused-variable]
  102 |  int sum=0,cnt=0,p=0;
      |      ^~~
reconstruction.cpp:102:12: warning: unused variable 'cnt' [-Wunused-variable]
  102 |  int sum=0,cnt=0,p=0;
      |            ^~~

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