oj.uz

답안 #925787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925787 2024-02-12T08:50:10 Z pcc Min-max tree (BOI18_minmaxtree) C++14
29 / 100
 250 ms 45812 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 7e4+10;
int idx[mxn],par[mxn],link_top[mxn],sz[mxn],dep[mxn],bs[mxn],cnt,ans[mxn];
vector<int> tree[mxn];
int N,Q;
map<int,int> mp,rmp;
set<int> used;

struct SEG{
	int seg[mxn*4];
	SEG(){
		memset(seg,-1,sizeof(seg));
	}
	void push(int now){
		if(seg[now] == -1)return;
		seg[now*2+2] = seg[now*2+1] = seg[now];
		seg[now] = -1;
		return;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now] = v;
			return;
		}
		int mid = (l+r)>>1;
		push(now);
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
	}
	int getval(int now,int l,int r,int p){
		if(l == r||seg[now] != -1)return seg[now];
		int mid = (l+r)>>1;
		if(mid>=p)return getval(now*2+1,l,mid,p);
		else return getval(now*2+2,mid+1,r,p);
	}
};

SEG mx,mn;
vector<pair<int,pii>> mxv,mnv;

struct DINIC{
	struct E{
		int t,c,f;
		E(){
			t = c= f = 0;
		}
		E(int tt,int cc):t(tt),c(cc),f(0){}
	};
	vector<E> e;
	vector<int> ptr,lvl;
	queue<int> q;
	vector<vector<int>> p;
	DINIC(int n = 0){
		ptr = lvl = vector<int>(n,0);
		e.clear();
		p = vector<vector<int>>(n);
	}
	void add_edge(int a,int b,int c,int d = 0){
		p[a].push_back(e.size());
		e.push_back(E(b,c));
		p[b].push_back(e.size());
		e.push_back(E(a,d));
		return;
	}
	bool bfs(int s,int t){
		fill(lvl.begin(),lvl.end(),-1);
		q.push(s);
		lvl[s] = 0;
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto &eid:p[now]){
				int nxt = e[eid].t;
				if(e[eid].f == e[eid].c||lvl[nxt] != -1)continue;
				lvl[nxt] = lvl[now]+1;
				q.push(nxt);
			}
		}
		return lvl[t] != -1;
	}
	int dfs(int now,int t,int f){
		if(now == t||!f)return f;
		for(int &i = ptr[now];i<p[now].size();i++){
			int eid = p[now][i];
			if(e[eid].c == e[eid].f||lvl[e[eid].t] != lvl[now]+1)continue;
			if(int re = dfs(e[eid].t,t,min(f,e[eid].c-e[eid].f))){
				e[eid].f += re;
				e[eid^1].f -= re;
				return re;
			}
		}
		return 0;
	}
	int flow(int s,int t){
		int ans = 0;
		while(bfs(s,t)){
			fill(ptr.begin(),ptr.end(),0);
			while(int re = dfs(s,t,INT_MAX))ans += re;
		}
		return ans;
	}
	void getans(){
		for(int i = 0;i<e.size();i+=2){
			if(e[i].f == e[i].c&&e[i].t>N&&e[i^1].t<=N){
				ans[e[i^1].t] = rmp[e[i].t-N];
			}
		}
	}
};

void dfs1(int now){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == par[now])continue;
		par[nxt] = now;
		dep[nxt] = dep[now]+1;
		dfs1(nxt);
		sz[now] += sz[nxt];
		if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
	}
	return;
}
void dfs2(int now,int top){
	link_top[now] = top;
	idx[now] = ++cnt;
	if(bs[now])dfs2(bs[now],top);
	for(auto nxt:tree[now]){
		if(nxt == par[now]||nxt == bs[now])continue;
		dfs2(nxt,nxt);
	}
	return;
}

inline void calc(int a,int b,int w,SEG &segtree){
	int ta = link_top[a],tb = link_top[b];
	while(ta != tb){
		if(dep[ta]<dep[tb]){
			swap(a,b);
			swap(ta,tb);
		}
		segtree.modify(0,1,N,idx[ta],idx[a],w);
		a = par[ta];
		ta = link_top[a];
	}
	if(idx[a]>idx[b])swap(a,b);
	if(a != b)segtree.modify(0,1,N,idx[a]+1,idx[b],w);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs1(1);
	dfs2(1,1);
	mx.modify(0,1,N,1,N,INT_MAX);
	mn.modify(0,1,N,1,N,0);
	cin>>Q;
	for(int i = 0;i<Q;i++){
		char c;
		int a,b,w;
		cin>>c>>a>>b>>w;
		used.insert(w);
		if(c == 'M')mxv.push_back({w,{a,b}});
		else mnv.push_back({w,{a,b}});
	}
	sort(mxv.rbegin(),mxv.rend());
	sort(mnv.begin(),mnv.end());
	for(auto &i:mxv)calc(i.sc.fs,i.sc.sc,i.fs,mx);
	for(auto &i:mnv)calc(i.sc.fs,i.sc.sc,i.fs,mn);
	DINIC din(N*5+2);
	for(int i = 2;i<=N;i++){
		int low = mn.getval(0,1,N,idx[i]),high = mx.getval(0,1,N,idx[i]);
		if(mp.find(low)==mp.end())mp[low] = mp.size()+1;
		if(mp.find(high)==mp.end())mp[high] = mp.size()+1;
		rmp[mp[low]] = low;
		rmp[mp[high]] = high;
		low = mp[low],high = mp[high];
		//cout<<i<<':'<<low<<','<<high<<":"<<rmp[low]<<','<<rmp[high]<<endl;
		if(used.find(rmp[low]) != used.end())din.add_edge(i,low+N,1);
		if(used.find(rmp[high]) != used.end())din.add_edge(i,high+N,1);
		din.add_edge(0,i,1);
		//cout<<i<<endl;
	}
	for(auto &i:used)din.add_edge(mp[i]+N,N*2,1);
	//cout<<"GRAPH MADE"<<endl;
	/*
	for(int i = 0;i<din.e.size();i+=2){
		cout<<din.e[i^1].t<<' '<<din.e[i].t<<endl;
	}
   */
	int tans = din.flow(0,N*2);
	assert(tans == Q);
	din.getans();
	for(int i = 2;i<=N;i++){
		cout<<par[i]<<' '<<i<<' '<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message

minmaxtree.cpp: In member function 'int DINIC::dfs(int, int, int)':
minmaxtree.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int &i = ptr[now];i<p[now].size();i++){
      |                         ~^~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'void DINIC::getans()':
minmaxtree.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DINIC::E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int i = 0;i<e.size();i+=2){
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 45812 KB Output is correct
2 Correct 243 ms 41216 KB Output is correct
3 Correct 215 ms 41224 KB Output is correct
4 Correct 250 ms 45564 KB Output is correct
5 Correct 224 ms 42240 KB Output is correct
6 Correct 238 ms 42836 KB Output is correct
7 Correct 231 ms 41228 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 148 ms 33916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 245 ms 45812 KB Output is correct
6 Correct 243 ms 41216 KB Output is correct
7 Correct 215 ms 41224 KB Output is correct
8 Correct 250 ms 45564 KB Output is correct
9 Correct 224 ms 42240 KB Output is correct
10 Correct 238 ms 42836 KB Output is correct
11 Correct 231 ms 41228 KB Output is correct
12 Incorrect 148 ms 33916 KB Output isn't correct
13 Halted 0 ms 0 KB -