Submission #63468

#	Time	Username	Problem	Language	Result	Execution time	Memory
63468		spencercompton	Min-max tree (BOI18_minmaxtree)	C++14	22 / 100	810 ms	75504 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;
int qwertyu = 69;
class Edge{
    public:
        long dest, revInd, cap, flow;
        Edge(long a, long b, long c){
            dest = a;
            revInd = b;
            cap = c;
            flow = 0;
        }
};
class Flow{
    public:
        vector<vector<Edge> > graph;
        vector<vector<Edge> > copy;
        Flow(long nodes){
            graph.resize(nodes);
        }
        void add(long s, long t){
        	long cap = 1;
            graph[s].push_back(Edge(t,graph[t].size(),cap));
            graph[t].push_back(Edge(s,graph[s].size()-1,0));
        }
        bool bfs(long src, long dest, long dist[]){
            for(long i = 0; i<copy.size(); i++){
                dist[i] = -1;
            }
            dist[src] = 0;
            long q[copy.size()];
            for(long i = 0; i<copy.size(); i++){
                q[i] = 0;
            }
            long pointer = 0;
            q[pointer++] = src;
            for(long i = 0; i<pointer; i++){
                long now = q[i];
                for(long j = 0; j<copy[now].size(); j++){
                    Edge e = copy[now][j];
                    if(dist[e.dest]<0 && e.flow<e.cap){
                        dist[e.dest] = dist[now]+1;
                        q[pointer++] = e.dest;
                    }
                }
            }
            return dist[dest] >=0;
        }
        int dfs(long pointer[], long dist[], long dest, long now, long flow){
            if(now==dest){
                return flow;
            }
            for(; pointer[now] < copy[now].size(); pointer[now]++){
                Edge e = copy[now][pointer[now]];
                if(dist[e.dest]==dist[now]+1 && e.flow<e.cap){
                    long added = dfs(pointer, dist, dest, e.dest, min(flow,e.cap-e.flow));
                    if(added>0){
                        copy[now][pointer[now]].flow += added;
                        copy[e.dest][e.revInd].flow -= added;
                        return added;
                    }
                }
            }
            return 0;
        }
        void copyGraph(){
            copy.resize(graph.size());
            for(long i = 0; i<graph.size(); i++){
                for(long j = 0; j<graph[i].size(); j++){
                    Edge e = graph[i][j];
                    copy[i].push_back(Edge(e.dest,e.revInd,e.cap));
                }
            }
        }
        long maxFlow(long src, long dest){
            copyGraph();
            long flow = 0;
            long dist[copy.size()];
            for(long i = 0; i<copy.size(); i++){
                dist[i] = 0;
            }
            while(bfs(src, dest, dist)){
                long pointer[copy.size()];
                for(long i = 0; i<copy.size(); i++){
                    pointer[i] = 0;
                }
                while(true){
                    long added = dfs(pointer, dist, dest, src, 2147483647L);
                    if(added==0){
                        break;
                    }
                    flow+=added;
                }
            }
            return flow;
        }
};
int maxi[70000];
int mini[70000];
int lc[18][70000];
vector<int> adj[70000];
set<int> maxs[70000];
set<int> mins[70000];
vector<int> remmax[70000];
vector<int> remmin[70000];
int h[70000];
int dfs1(int now, int from, int x){
	lc[0][now] = from;
	h[now] = x;
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		dfs1(to,now,x+1);
	}
}
int mgmin(int a, int b){
	if(mins[a].size()>mins[b].size()){
		swap(a,b);
	}
	for(auto it = mins[a].begin(); it!=mins[a].end(); it++){
		mins[b].insert(*it);
	}
	mins[a].clear();
	return b;
}
int mgmax(int a, int b){
	if(maxs[a].size()>maxs[b].size()){
		swap(a,b);
	}
	for(auto it = maxs[a].begin(); it!=maxs[a].end(); it++){
		maxs[b].insert(*it);
	}
	maxs[a].clear();
	return b;
}
int lca(int a, int b){
	if(a==b){
		return a;
	}
	if(h[a] < h[b]){
		swap(a,b);
	}
	for(int i = 17; i>=0; i--){
		if(lc[i][a]!=-1 && h[lc[i][a]]>=h[b]){
			a = lc[i][a];
		}
	}
	if(a==b){
		return a;
	}
	for(int i = 17; i>=0; i--){
		int toa = lc[i][a];
		int tob = lc[i][b];
		if(toa!=tob){
			a = toa;
			b = tob;
		}
	}
	return lc[0][a];
}
pair<int, int> go(int now, int from){
	//returns minid, maxid
	pair<int, int> ret = make_pair(now,now);
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		pair<int, int> got = go(to,now);
		ret.first = mgmin(ret.first,got.first);
		ret.second = mgmax(ret.second,got.second);
	}
	for(int i = 0; i<remmax[now].size(); i++){
		maxs[ret.second].erase(maxs[ret.second].find(remmax[now][i]));
	}
	for(int i = 0; i<remmin[now].size(); i++){
		mins[ret.first].erase(mins[ret.first].find(remmin[now][i]));
	}
	if(maxs[ret.second].size()>0){
		maxi[now] = *maxs[ret.second].begin();
	}
	else{
		maxi[now] = -1;
	}
	if(mins[ret.first].size()>0){
		mini[now] = *mins[ret.first].rbegin();
	}
	else{
		mini[now] = -1;
	}
	return ret;
}
int main(){
	// cout << "MAIN " << endl;
	// Flow f = Flow();
	// cout << "X " << endl;
	// f.add(0,1);
	// f.add(0,4);
	// f.add(0,69);
	// f.add(69,42);
	// f.add(42,13);
	// f.add(42,1);
	// cout << "Y " << endl;
	// cout << f.flow() << endl;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i<n; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs1(0,-1,0);
	for(int i = 1; i<18; i++){
		for(int j = 0; j<n; j++){
			if(lc[i-1][j]==-1){
				lc[i][j] = -1;
			}
			else{
				lc[i][j] = lc[i-1][lc[i-1][j]];
			}
		}
	}
	int q;
	cin >> q;
	for(int i = 0; i<q; i++){
		string s;
		int a, b, v;
		cin >> s >> a >> b >> v;
		a--;
		b--;
		int l = lca(a,b);
		if(s=="M"){
			//maxi
			maxs[a].insert(v);
			maxs[b].insert(v);
			remmax[l].push_back(v);
		}
		else{
			mins[a].insert(v);
			mins[b].insert(v);
			remmin[l].push_back(v);
		}
	}
	go(0,-1);
	map<int, int> m;
	map<int, int> rev;
	int point = 2+n;
	Flow f = Flow(point+n);
	for(int i = 1; i<n; i++){
		if(mini[i]!=-1 && m.find(mini[i])==m.end()){
			rev[point] = mini[i];
			f.add(point,1);
			m[mini[i]] = point++;
		}
		if(maxi[i]!=-1 && m.find(maxi[i])==m.end()){
			rev[point] = maxi[i];
			f.add(point,1);
			m[maxi[i]] = point++;
		}
	}
	for(int i = 1; i<n; i++){
		f.add(0,2+i);
		if(mini[i]!=-1){
			f.add(2+i,m[mini[i]]);
		}
		if(maxi[i]!=-1){
			f.add(2+i,m[maxi[i]]);
		}
	}
	f.maxFlow(0,1);
	for(int i = 1; i<n; i++){
		int found = -1;
		for(int j = 0; j<f.copy[2+i].size(); j++){
			int to = f.copy[2+i][j].dest;
			if(to!=0 && f.copy[2+i][j].cap==0){
				found = rev[to];
			}
		}
		cout << (i+1) << " " << (lc[0][i]+1) << " ";
		if(found!=-1){
			cout << found << "\n";
		}
		else if(maxi[i]!=-1){
			cout << maxi[i] << "\n";
		}
		else if(mini[i]!=-1){
			cout << mini[i] << "\n";
		}
		else{
			cout << 69 << "\n";
		}
	}
}

Compilation message (stderr)

minmaxtree.cpp: In member function 'bool Flow::bfs(long int, long int, long int*)':
minmaxtree.cpp:27:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(long i = 0; i<copy.size(); i++){
                             ~^~~~~~~~~~~~
minmaxtree.cpp:32:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(long i = 0; i<copy.size(); i++){
                             ~^~~~~~~~~~~~
minmaxtree.cpp:39:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(long j = 0; j<copy[now].size(); j++){
                                 ~^~~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int Flow::dfs(long int*, long int*, long int, long int, long int)':
minmaxtree.cpp:53:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; pointer[now] < copy[now].size(); pointer[now]++){
                   ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'void Flow::copyGraph()':
minmaxtree.cpp:68:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(long i = 0; i<graph.size(); i++){
                             ~^~~~~~~~~~~~~
minmaxtree.cpp:69:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(long j = 0; j<graph[i].size(); j++){
                                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'long int Flow::maxFlow(long int, long int)':
minmaxtree.cpp:79:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(long i = 0; i<copy.size(); i++){
                             ~^~~~~~~~~~~~
minmaxtree.cpp:84:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(long i = 0; i<copy.size(); i++){
                                 ~^~~~~~~~~~~~
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:110:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:117:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
minmaxtree.cpp: In function 'std::pair<int, int> go(int, int)':
minmaxtree.cpp:166:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:175:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmax[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:178:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmin[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:280:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<f.copy[2+i].size(); j++){
                  ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42