oj.uz

Submission #555715

# Submission time Handle Problem Language Result Execution time Memory
555715 2022-05-01T11:47:34 Z Koosha_mv Reconstruction Project (JOI22_reconstruction) C++14
70 / 100
 5000 ms 22688 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 2327 ms 13728 KB Output is correct
21 Correct 1214 ms 12112 KB Output is correct
22 Correct 1964 ms 12104 KB Output is correct
23 Correct 2130 ms 12228 KB Output is correct
24 Correct 2234 ms 12056 KB Output is correct
25 Correct 2220 ms 12076 KB Output is correct
26 Correct 2281 ms 13708 KB Output is correct
27 Correct 2284 ms 13716 KB Output is correct
28 Correct 2261 ms 13628 KB Output is correct
29 Correct 1161 ms 13824 KB Output is correct
30 Correct 2295 ms 13696 KB Output is correct
31 Correct 2291 ms 13716 KB Output is correct
32 Correct 2278 ms 13684 KB Output is correct
33 Correct 2279 ms 12080 KB Output is correct
34 Correct 1084 ms 15692 KB Output is correct
35 Correct 2287 ms 13832 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Execution timed out 5062 ms 14880 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1564 ms 22108 KB Output is correct
21 Correct 1697 ms 17332 KB Output is correct
22 Correct 1632 ms 21824 KB Output is correct
23 Correct 1629 ms 22296 KB Output is correct
24 Correct 1544 ms 22392 KB Output is correct
25 Correct 1542 ms 22080 KB Output is correct
26 Correct 1572 ms 22204 KB Output is correct
27 Correct 1629 ms 22344 KB Output is correct
28 Correct 1517 ms 22248 KB Output is correct
29 Correct 1594 ms 22208 KB Output is correct
30 Correct 1598 ms 22076 KB Output is correct
31 Correct 1615 ms 22084 KB Output is correct
32 Correct 1679 ms 22688 KB Output is correct
33 Correct 1595 ms 22164 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 2327 ms 13728 KB Output is correct
21 Correct 1214 ms 12112 KB Output is correct
22 Correct 1964 ms 12104 KB Output is correct
23 Correct 2130 ms 12228 KB Output is correct
24 Correct 2234 ms 12056 KB Output is correct
25 Correct 2220 ms 12076 KB Output is correct
26 Correct 2281 ms 13708 KB Output is correct
27 Correct 2284 ms 13716 KB Output is correct
28 Correct 2261 ms 13628 KB Output is correct
29 Correct 1161 ms 13824 KB Output is correct
30 Correct 2295 ms 13696 KB Output is correct
31 Correct 2291 ms 13716 KB Output is correct
32 Correct 2278 ms 13684 KB Output is correct
33 Correct 2279 ms 12080 KB Output is correct
34 Correct 1084 ms 15692 KB Output is correct
35 Correct 2287 ms 13832 KB Output is correct
36 Correct 3807 ms 14148 KB Output is correct
37 Correct 2991 ms 14096 KB Output is correct
38 Correct 3555 ms 12352 KB Output is correct
39 Correct 3761 ms 12420 KB Output is correct
40 Correct 3690 ms 12652 KB Output is correct
41 Correct 3834 ms 12544 KB Output is correct
42 Correct 3768 ms 13472 KB Output is correct
43 Correct 3751 ms 13704 KB Output is correct
44 Correct 3874 ms 14208 KB Output is correct
45 Correct 2913 ms 14244 KB Output is correct
46 Correct 4037 ms 14232 KB Output is correct
47 Correct 4034 ms 14124 KB Output is correct
48 Correct 3882 ms 13840 KB Output is correct
49 Correct 3788 ms 12316 KB Output is correct
50 Correct 2452 ms 14156 KB Output is correct
51 Correct 3644 ms 12420 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 2327 ms 13728 KB Output is correct
21 Correct 1214 ms 12112 KB Output is correct
22 Correct 1964 ms 12104 KB Output is correct
23 Correct 2130 ms 12228 KB Output is correct
24 Correct 2234 ms 12056 KB Output is correct
25 Correct 2220 ms 12076 KB Output is correct
26 Correct 2281 ms 13708 KB Output is correct
27 Correct 2284 ms 13716 KB Output is correct
28 Correct 2261 ms 13628 KB Output is correct
29 Correct 1161 ms 13824 KB Output is correct
30 Correct 2295 ms 13696 KB Output is correct
31 Correct 2291 ms 13716 KB Output is correct
32 Correct 2278 ms 13684 KB Output is correct
33 Correct 2279 ms 12080 KB Output is correct
34 Correct 1084 ms 15692 KB Output is correct
35 Correct 2287 ms 13832 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Execution timed out 5062 ms 14880 KB Time limit exceeded
40 Halted 0 ms 0 KB -