oj.uz

Submission #118301

# Submission time Handle Problem Language Result Execution time Memory
118301 2019-06-18T15:44:10 Z KLPP Simurgh (IOI17_simurgh) C++14
19 / 100
 102 ms 4708 KB 
#include "simurgh.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
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)
int road[500][500];
int deg[500];
int parent[500];
vector<int> answer;
int N;
void solve(){
  int vertex=0;
  vector<int> leaves;
  vector<int> others;
  rep(i,0,N){
    if(deg[i]>0){
      vertex++;
      if(deg[i]==1)leaves.push_back(i);
      if(deg[i]>1)others.push_back(i);
    }
  }
  if(vertex==2){
    answer.push_back(road[leaves[0]][leaves[1]]);
    return;
  }
  if(leaves.size()==vertex-1){
    int top=-1;
    rep(i,0,N){
      if(deg[i]>1)top=i;
    }
    trav(a,leaves){
      answer.push_back(road[a][top]);
    }
    return;
  }
  /*trav(a,leaves)cout<<a<<" ";
  cout<<endl;*/
  vector<int> add;
  vector<int> L;
  for(int i=0;i<leaves.size()-1;i++)L.push_back(road[leaves[i]][leaves[i+1]]);
  for(int i=0;i<leaves.size()-1;i++){
    int u,v;
    u=leaves[i];
    v=leaves[i+1];
    int attempt=0;
    int got=answer.size()+1;
    while(attempt<20 && got==answer.size()+1){
      attempt++;
      vector<int> q;
      trav(r,answer)q.push_back(r);
      trav(r,L)q.push_back(r);
      random_shuffle(others.begin(),others.end());
      int mid=others.size()/2;
      rep(j,0,others.size()){
	if(j<mid)q.push_back(road[u][others[j]]);
	else q.push_back(road[v][others[j]]);
      }
      got=count_common_roads(q);
      /*trav(a,q)cout<<a<<" ";
	cout<<endl<<got<<endl;*/
    }
    /*trav(V,others)cout<<V<<" ";
    cout<<endl;
      cout<<got<<" "<<u<<" "<<v<<endl;*/
    if(got==answer.size()+1){
      if(parent[u]!=-1){
	add.push_back(road[v][parent[u]]);
	parent[v]=parent[u];
      }
    }else{
      int lo=0;
      int hi=others.size()/2;
      //cout<<lo<<" "<<hi<<endl;
      while(hi-lo>1){
	int mid=(hi+lo)/2;
	vector<int> q;
	trav(r,answer)q.push_back(r);
	trav(r,L)q.push_back(r);
	rep(j,0,others.size()){
	  if(j<mid)q.push_back(road[u][others[j]]);
	  else q.push_back(road[v][others[j]]);
	}
	int A=count_common_roads(q);
	if(A==answer.size()+1){
	  lo=mid;
	}else hi=mid;
      }
      
      //cout<<got<<" "<<road[u][others[lo]]<<endl;
      if(got>answer.size()+1){
	if(parent[u]==-1){
	  rep(k,0,i+1){
	    add.push_back(road[leaves[k]][others[lo]]);
	    parent[leaves[k]]=others[lo];
	  }
	}
	
      }
      if(got<answer.size()+1){
	add.push_back(road[v][others[lo]]);
	parent[v]=others[lo];
      }
      lo=others.size()/2;
      hi=others.size();
      
      while(hi-lo>1){
	int mid=(hi+lo)/2;
	vector<int> q;
	trav(r,answer)q.push_back(r);
	trav(r,L)q.push_back(r);
	rep(j,0,others.size()){
	  if(j<mid)q.push_back(road[u][others[j]]);
	  else q.push_back(road[v][others[j]]);
	}
	int A=count_common_roads(q);
	//cout<<A<<endl;
	if(A==answer.size()+1){
	  hi=mid;
	}else lo=mid;
      }
      //cout<<lo<<" "<<hi<<endl;
      //cout<<got<<" "<<road[u][others[lo]]<<endl;
      if(got<answer.size()+1){
	if(parent[u]==-1){
	  rep(k,0,i+1){
	    add.push_back(road[leaves[k]][others[lo]]);
	    parent[leaves[k]]=others[lo];
	  }
	}
	
      }
      if(got>answer.size()+1){
	add.push_back(road[v][others[lo]]);
	parent[v]=others[lo];
      }
    }
  }
  //cout<<"A"<<endl;
  trav(r,add)answer.push_back(r);
  trav(l,leaves){
    deg[l]--;
    deg[parent[l]]--;
  }
  solve();
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
  N=n;
  rep(i,0,n)road[i][i]=-1;
  rep(i,0,u.size()){
    road[u[i]][v[i]]=i;
    road[v[i]][u[i]]=i;
  }
  rep(i,0,n){
    parent[i]=-1;
    vector<int> q;
    rep(j,0,n){
      if(i!=j)q.push_back(road[i][j]);
    }
    deg[i]=count_common_roads(q);
  }
  solve();
  /*trav(r,answer)cout<<r<<" ";
    cout<<endl;*/
  return answer;
}

Compilation message

simurgh.cpp: In function 'void solve()':
simurgh.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(leaves.size()==vertex-1){
      ~~~~~~~~~~~~~^~~~~~~~~~
simurgh.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<leaves.size()-1;i++)L.push_back(road[leaves[i]][leaves[i+1]]);
               ~^~~~~~~~~~~~~~~~
simurgh.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<leaves.size()-1;i++){
               ~^~~~~~~~~~~~~~~~
simurgh.cpp:51:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(attempt<20 && got==answer.size()+1){
                         ~~~^~~~~~~~~~~~~~~~~
simurgh.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:58:11:
       rep(j,0,others.size()){
           ~~~~~~~~~~~~~~~~~      
simurgh.cpp:58:7: note: in expansion of macro 'rep'
       rep(j,0,others.size()){
       ^~~
simurgh.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(got==answer.size()+1){
        ~~~^~~~~~~~~~~~~~~~~
simurgh.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:83:6:
  rep(j,0,others.size()){
      ~~~~~~~~~~~~~~~~~           
simurgh.cpp:83:2: note: in expansion of macro 'rep'
  rep(j,0,others.size()){
  ^~~
simurgh.cpp:88:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(A==answer.size()+1){
     ~^~~~~~~~~~~~~~~~~
simurgh.cpp:94:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(got>answer.size()+1){
          ~~~^~~~~~~~~~~~~~~~
simurgh.cpp:103:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(got<answer.size()+1){
          ~~~^~~~~~~~~~~~~~~~
simurgh.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:115:6:
  rep(j,0,others.size()){
      ~~~~~~~~~~~~~~~~~           
simurgh.cpp:115:2: note: in expansion of macro 'rep'
  rep(j,0,others.size()){
  ^~~
simurgh.cpp:121:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(A==answer.size()+1){
     ~^~~~~~~~~~~~~~~~~
simurgh.cpp:127:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(got<answer.size()+1){
          ~~~^~~~~~~~~~~~~~~~
simurgh.cpp:136:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(got>answer.size()+1){
          ~~~^~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
simurgh.cpp:153:7:
   rep(i,0,u.size()){
       ~~~~~~~~~~~~               
simurgh.cpp:153:3: note: in expansion of macro 'rep'
   rep(i,0,u.size()){
   ^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 72 ms 2944 KB correct
4 Correct 100 ms 4348 KB correct
5 Correct 98 ms 4216 KB correct
6 Correct 33 ms 4216 KB correct
7 Correct 102 ms 4280 KB correct
8 Correct 100 ms 4216 KB correct
9 Correct 85 ms 4344 KB correct
10 Correct 80 ms 4472 KB correct
11 Correct 100 ms 4344 KB correct
12 Correct 70 ms 4708 KB correct
13 Correct 2 ms 384 KB correct
14 Correct 61 ms 4224 KB correct
15 Correct 73 ms 4600 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Incorrect 2 ms 384 KB WA in grader: NO
5 Halted 0 ms 0 KB -