oj.uz

Submission #97836

# Submission time Handle Problem Language Result Execution time Memory
97836 2019-02-18T19:12:40 Z KLPP ICC (CEOI16_icc) C++14
0 / 100
 394 ms 632 KB 
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long int lld;
set<pair<int,int> >S;
int arr1[1000];
int arr2[1000];
int q(vector<int> a, vector<int> b){
	for(int i=0;i<a.size();i++)arr1[i]=a[i];
	for(int i=0;i<b.size();i++)arr2[i]=b[i];
	return query(a.size(),b.size(),arr1,arr2);
}
vector<vector<int> > CC;
pair<int,int> discover_edge(vector<int> a, vector<int> b){
	if(a.size()==1 && b.size()==1)return pair<int,int>(a[0],b[0]);
	if(a.size()<b.size())swap(a,b);
	vector<int> mid;
	int M=a.size()/2;
	for(int i=0;i<M;i++)mid.push_back(a[i]);
	if(q(mid,b)){
		return discover_edge(mid,b);
	}
	mid.clear();
	for(int i=M;i<a.size();i++)mid.push_back(a[i]);
	return discover_edge(mid,b);
}
int test_components(int a, int b){
	return q(CC[a],CC[b]);
}
void merge_components(int a, int b){
	if(a<b)swap(a,b);
	vector<int> v1;
	for(int i=0;i<CC[a].size();i++)v1.push_back(CC[a][i]);
	for(int i=0;i<CC[b].size();i++)v1.push_back(CC[b][i]);
	CC.erase(CC.begin()+a);
	CC.erase(CC.begin()+b);
	CC.push_back(v1);
}
void run(int N){
	if(CC.size()==0){
		for(int i=1;i<=N;i++){
			vector<int> v;
			v.push_back(i);
			CC.push_back(v);
		}
	}
	/*for(int i=0;i<CC.size();i++){
		for(int j=0;j<CC[i].size();j++)cout<<CC[i][j]<<" ";
		cout<<endl;
	}*/
	for(int i=0;i<CC.size();i++){
		for(int j=i+1;j<CC.size();j++){
			if(test_components(i,j)){
				pair<int,int> p=discover_edge(CC[i],CC[j]);
				merge_components(i,j);
				setRoad(p.first,p.second);
				return;
			}
		}
	}
	
	
}

Compilation message

icc.cpp: In function 'int q(std::vector<int>, std::vector<int>)':
icc.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)arr1[i]=a[i];
              ~^~~~~~~~~
icc.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();i++)arr2[i]=b[i];
              ~^~~~~~~~~
icc.cpp: In function 'std::pair<int, int> discover_edge(std::vector<int>, std::vector<int>)':
icc.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=M;i<a.size();i++)mid.push_back(a[i]);
              ~^~~~~~~~~
icc.cpp: In function 'void merge_components(int, int)':
icc.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<CC[a].size();i++)v1.push_back(CC[a][i]);
              ~^~~~~~~~~~~~~
icc.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<CC[b].size();i++)v1.push_back(CC[b][i]);
              ~^~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<CC.size();i++){
              ~^~~~~~~~~~
icc.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<CC.size();j++){
                 ~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 512 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 564 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 323 ms 604 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 394 ms 632 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 251 ms 512 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 608 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -