Submission #119188

#	Time	Username	Problem	Language	Result	Execution time	Memory
119188		KLPP	Meetings (JOI19_meetings)	C++14	29 / 100	3030 ms	2844 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
vector<pair<int,int> >edges;

/*void solve(vector<int> v){
  if(v.size()==1)return;
  if(v.size()==2){
    edges.push_back(pii(v[0],v[1]));
    return;
  }
  random_shuffle(v.begin(),v.end());
  int x=v[0];
  int y=v[1];
  cout<<x<<" "<<y<<endl;
  int answer[v.size()];
  answer[0]=-1;
  answer[1]=-1;
  map<int,vector<int> >m;
  rep(i,0,v.size()){
    vector<int> N;
    m[i]=N;
  }
  rep(i,2,v.size()){
    answer[i]=Query(x,y,v[i]);
    m[answer[i]].push_back(v[i]);
  }
  set<int> line;
  line.insert(x);
  line.insert(y);
  trav(p,m){
    if(p.second.size()>0){
      solve(p.second);
      line.insert(p.first);
    }
  }
  trav(l,line){
    cout<<l<<endl;
  }
}*/
void Solve(int N) {
  /*vector<int> test;
  rep(i,0,N)test.push_back(i);
  solve(test);*/
  int answer[N][N];
  set<int> parents[N];
  bool leaf[N];
  rep(i,0,N)leaf[i]=true;
  rep(i,0,N)parents[i].insert(0);
  rep(i,1,N){
    rep(j,1,N){
      if(i<j){
	answer[i][j]=Query(0,i,j);
	parents[i].insert(answer[i][j]);
	parents[j].insert(answer[i][j]);
	leaf[answer[i][j]]=false;
      }
    }
  }
  rep(i,1,N){
    trav(a,parents[i]){
      //cout<<a<<" ";
      if(!leaf[i] && parents[a].size()==parents[i].size()-1){
	//Bridge(a,i);
	//cout<<a<<" "<<i<<endl;
	Bridge(min(a,i),max(a,i));
      }
      if(leaf[i] && parents[a].size()==parents[i].size()){
	//cout<<a<<" "<<i<<endl;
	Bridge(min(a,i),max(a,i));
      }
    }//cout<<endl;
  }
  
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71