제출 #63472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63472		spencercompton	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	857 ms	113208 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;

class Edge
   {
   public:
      int i, j, cap;
      Edge *rev;

      Edge(int ii, int jj, int capp)
      {
         i = ii;
         j = jj;
         cap = capp;
         rev = NULL;
      }
      Edge(){

      }
   };
class IsapSolver 
{
public:
   int numNodes, source, sink; 
   vector<vector<Edge* > > adj;
   
   deque<int> q;
   deque<Edge*> path;
   vector<int> level;
   vector<int> curEdge;
   vector<int> count;

   IsapSolver(int numNodess)
   {
      numNodes = numNodess;
      source = 0;
      sink = 1;
      for (int i=0; i<numNodes; i++)
      {
         vector<Edge*> x;
         adj.push_back(x);
      }
      
      level.resize(numNodes);
      curEdge.resize(numNodes);
      count.resize(numNodes+1);
   }

   void add(int i, int j)
   {
   	  int cap = 1;
      Edge* fwd = new Edge(i, j, cap);
      Edge* rev = new Edge(j, i, 0);
      fwd->rev = rev;
      rev->rev = fwd;
      adj[i].push_back(fwd);
      adj[j].push_back(rev);
   }

   void bfs()
   {
      for(int i = 0; i<numNodes; i++){
         level[i] = -1;
      }
      level[sink] = 0;
      q.clear();
      q.push_back(sink);

      while (!q.empty())
      {
         //poll
         int i = q.front();
         q.pop_front();
         for (Edge* e : adj[i])
         {
            if (e->rev->cap > 0 && level[e->j] == -1)
            {
               level[e->j] = level[i] + 1;
               q.push_back(e->j);
            }
         }
      }
   }

   int run()
   {
      bfs();
      for (int i=0; i<numNodes; i++)
         count[level[i]]++;

      int i = source;
      int totalFlow = 0;
      while (level[source] < numNodes)
      {
         Edge *admissibleEdge = NULL;
         while (curEdge[i] < adj[i].size())
         {
            Edge* e = adj[i][curEdge[i]];
            if (level[i] == level[e->j] + 1 && e->cap > 0)
            {
               admissibleEdge = e;
               break;
            }

            curEdge[i]++;
         }

         if (admissibleEdge == NULL)
         {
            // Relabel & Retreat
            count[level[i]]--;
            if (count[level[i]] == 0)
               return totalFlow;
            level[i] = numNodes;
            for (Edge* e : adj[i])
               if (e->cap > 0)
                  level[i] = min(level[i], 1+level[e->j]);
            count[level[i]]++;
            curEdge[i] = 0;
            if (i != source)
            {
               //pop
               Edge* e = path.front();
               path.pop_front();
               i = e->i;
            }
         }
         else
         {
            path.push_back(admissibleEdge);
            i = admissibleEdge->j;
            if (i == sink)
            {
               int bottleneck = 2147483647;
               for (Edge* e : path)
                  bottleneck = min(bottleneck, e->cap);
               totalFlow += bottleneck;

               for (Edge* e : path)
               {
                  e->cap -= bottleneck;
                  e->rev->cap += bottleneck;
               }
            
               path.clear();
               i = source;
            }
         }
      }
      return totalFlow;
   }

   
};



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;
	IsapSolver f = IsapSolver(2 + n + q);
	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.run();
	for(int i = 1; i<n; i++){
		int found = -1;
		for(int j = 0; j<f.adj[2+i].size(); j++){
			int to = f.adj[2+i][j]->j;
			if(to!=0 && f.adj[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";
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

minmaxtree.cpp: In member function 'int IsapSolver::run()':
minmaxtree.cpp:96:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          while (curEdge[i] < adj[i].size())
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:170:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:177: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:226:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:235:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmax[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:238: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:340:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<f.adj[2+i].size(); j++){
                  ~^~~~~~~~~~~~~~~~~~

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