oj.uz

답안 #551428

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551428 2022-04-20T15:53:03 Z inksamurai Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 16936 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3xxEYjy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

struct dsu{
	int n,cmps;
	vector<int> par,siz;
	dsu(int m){init(m);}
	void init(int m){
		n=m;
		cmps=m;
		par.resize(n,0);
		siz.resize(n,0);
		for(int i=0;i<n;i++){
			par[i]=i;
			siz[i]=1;
		}
	}
	void merge(int v,int u){
		v=parent(v),u=parent(u);
		if(v==u)return;
		cmps--;
		if(siz[v]<siz[u])swap(v,u);
		siz[v]+=siz[u];
		par[u]=v;
	}
	int parent(int v){
		return par[v]==v?v:parent(par[v]);
	}
	bool same(int v, int u){
		return parent(v)==parent(u);
	}
	int size(int v=-1){
		return (v==-1?cmps:siz[parent(v)]);
	}
};

signed main(){
_3xxEYjy;
	int n,m;
	cin>>n>>m;

	using tpii=pair<int,pii>;
	vec(tpii) edges;
	rep(i,m){
		int u,v,w;
		cin>>u>>v>>w;
		u-=1,v-=1;
		edges.pb({w,{u,v}});
	}
	sort(edges.begin(),edges.end());

	const int inf=1e10;
	vec(tpii) evts;
	rep(i,m){
		dsu uf(n);
		int r=inf;
		rng(j,i+1,m){
			uf.merge(edges[j].se.fi,edges[j].se.se);
			if(uf.same(edges[i].se.fi,edges[i].se.se)){
				r=edges[j].fi;
				break;
			}
		}
		uf.init(n);
		int l=-inf;
		per(j,i){
			uf.merge(edges[j].se.fi,edges[j].se.se);
			if(uf.same(edges[i].se.fi,edges[i].se.se)){
				l=edges[j].fi;
				break;
			}
		}
		evts.pb({l==-inf?-1:(l+edges[i].fi+1)/2,{1,i}});
		evts.pb({r==inf?inf:(r+edges[i].fi+1)/2,{-1,i}});
	}
	sort(evts.begin(),evts.end(),[&](tpii l,tpii r){
		if(l.fi!=r.fi){
			return l.fi<r.fi;
		}else{
			return l.se.fi>r.se.fi;
		}
	});

	// for(auto tp:evts){
	// 	print(tp.fi,tp.se.fi,edges[tp.se.se].fi);
	// }

	int q;
	cin>>q;
	int i=-1;
	set<int> st;
	rep(_,q){
		int x;
		cin>>x;
		while(i+1<sz(evts) and evts[i+1].fi<=x){
			i+=1;
			if(evts[i].se.fi==1){
				st.insert(evts[i].se.se);
			}else{
				assert(st.find(evts[i].se.se)!=st.end());
				st.erase(st.find(evts[i].se.se));
			}
		}
		dsu uf(n);
		int res=0;
		for(auto id:st){
			// print(edges[id].fi);
			res+=abs(edges[id].fi-x);
		}
		cout<<res<<"\n";
		// break;
	}
//	
	return 0;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2001 ms 8892 KB Output is correct
21 Correct 1250 ms 8936 KB Output is correct
22 Correct 1399 ms 8928 KB Output is correct
23 Correct 1559 ms 9028 KB Output is correct
24 Correct 1884 ms 9052 KB Output is correct
25 Correct 2028 ms 9080 KB Output is correct
26 Correct 1980 ms 8940 KB Output is correct
27 Correct 2029 ms 9112 KB Output is correct
28 Correct 1942 ms 8864 KB Output is correct
29 Correct 852 ms 8888 KB Output is correct
30 Correct 1972 ms 10704 KB Output is correct
31 Correct 1970 ms 10592 KB Output is correct
32 Correct 1976 ms 10584 KB Output is correct
33 Correct 1917 ms 8888 KB Output is correct
34 Correct 600 ms 10504 KB Output is correct
35 Correct 1925 ms 10704 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 5037 ms 16936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 4161 ms 12780 KB Output is correct
21 Correct 4110 ms 12888 KB Output is correct
22 Correct 4158 ms 12756 KB Output is correct
23 Correct 4210 ms 12848 KB Output is correct
24 Correct 4101 ms 12892 KB Output is correct
25 Correct 4169 ms 12736 KB Output is correct
26 Correct 4226 ms 12600 KB Output is correct
27 Correct 4177 ms 12656 KB Output is correct
28 Correct 4179 ms 12820 KB Output is correct
29 Correct 4144 ms 12764 KB Output is correct
30 Correct 4212 ms 12736 KB Output is correct
31 Correct 4185 ms 12704 KB Output is correct
32 Correct 4343 ms 13196 KB Output is correct
33 Correct 4059 ms 12436 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2001 ms 8892 KB Output is correct
21 Correct 1250 ms 8936 KB Output is correct
22 Correct 1399 ms 8928 KB Output is correct
23 Correct 1559 ms 9028 KB Output is correct
24 Correct 1884 ms 9052 KB Output is correct
25 Correct 2028 ms 9080 KB Output is correct
26 Correct 1980 ms 8940 KB Output is correct
27 Correct 2029 ms 9112 KB Output is correct
28 Correct 1942 ms 8864 KB Output is correct
29 Correct 852 ms 8888 KB Output is correct
30 Correct 1972 ms 10704 KB Output is correct
31 Correct 1970 ms 10592 KB Output is correct
32 Correct 1976 ms 10584 KB Output is correct
33 Correct 1917 ms 8888 KB Output is correct
34 Correct 600 ms 10504 KB Output is correct
35 Correct 1925 ms 10704 KB Output is correct
36 Correct 2048 ms 10840 KB Output is correct
37 Correct 1329 ms 10920 KB Output is correct
38 Correct 1405 ms 9008 KB Output is correct
39 Correct 1575 ms 9176 KB Output is correct
40 Correct 1921 ms 8964 KB Output is correct
41 Correct 2039 ms 9016 KB Output is correct
42 Correct 2021 ms 9996 KB Output is correct
43 Correct 2001 ms 10288 KB Output is correct
44 Correct 2037 ms 10848 KB Output is correct
45 Correct 941 ms 10940 KB Output is correct
46 Correct 2035 ms 10772 KB Output is correct
47 Correct 2052 ms 10876 KB Output is correct
48 Correct 2020 ms 10504 KB Output is correct
49 Correct 2055 ms 8892 KB Output is correct
50 Correct 673 ms 8896 KB Output is correct
51 Correct 2016 ms 9148 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2001 ms 8892 KB Output is correct
21 Correct 1250 ms 8936 KB Output is correct
22 Correct 1399 ms 8928 KB Output is correct
23 Correct 1559 ms 9028 KB Output is correct
24 Correct 1884 ms 9052 KB Output is correct
25 Correct 2028 ms 9080 KB Output is correct
26 Correct 1980 ms 8940 KB Output is correct
27 Correct 2029 ms 9112 KB Output is correct
28 Correct 1942 ms 8864 KB Output is correct
29 Correct 852 ms 8888 KB Output is correct
30 Correct 1972 ms 10704 KB Output is correct
31 Correct 1970 ms 10592 KB Output is correct
32 Correct 1976 ms 10584 KB Output is correct
33 Correct 1917 ms 8888 KB Output is correct
34 Correct 600 ms 10504 KB Output is correct
35 Correct 1925 ms 10704 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Execution timed out 5037 ms 16936 KB Time limit exceeded
40 Halted 0 ms 0 KB -