Submission #804163

#	Time	Username	Problem	Language	Result	Execution time	Memory
804163		ngrace	Simurgh (IOI17_simurgh)	C++14	19 / 100	116 ms	4308 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;
#define ve vector
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second

int N;
set<int> ans;

int edgeInd[500][500];

int treeCount = 0;
bool treeEdges[500];
void initTree(){
	ve<int> edges;
	for(int i=0; i<N-1; i++) edges.push_back(edgeInd[i][i+1]);
	treeCount = count_common_roads(edges);
	
	for(int i=0; i<N-2; i++){
		edges[i] = edgeInd[i][i+2];
		int one = count_common_roads(edges);
		edges[i] = edgeInd[i][i+1];
		edges[i+1] = edgeInd[i][i+2];
		int two = count_common_roads(edges);
		edges[i+1] = edgeInd[i+1][i+2];

		if(one < max(treeCount, two)) treeEdges[i] = true;
		if(two < max(one, treeCount)) treeEdges[i+1] = true;
	}

	int su = 0;
	for(int i=0; i<N-1; i++) su += treeEdges[i];
	assert(su == treeCount);
}

int deg[500];
void calcDeg(int x){
	ve<int> edges;
	for(int i=0; i<N; i++){
		if(i==x) continue;
		edges.push_back(edgeInd[i][x]);
	}
	int one = (x==0) ? 0 : treeEdges[x-1];
	int two = (x==N-1) ? 0 : treeEdges[x];
	if(one) ans.insert(edgeInd[x-1][x]);
	deg[x] = count_common_roads(edges) - one - two;
}

void solve(){
	stack<int> s;
	for(int i=0; i<N; i++){
		if(deg[i]==1) s.push(i);
	}

	// cout <<"initial edges: ";
	// for(int i:ans) cout<<i<<" ";
	// cout<<endl;

	while(ans.size()<N-1){
		int x = s.top();
		s.pop();
		if(deg[x]==0) continue;

		// cout << "current leaf: " << x<<endl;
		int l=0, r=N-1;
		while(l<r){
			int m=(l+r)/2;
			ve<int> edges;
			int trCount = 0;
			for(int i=0; i < ((x<l) ? l-1 : l); i++){
				edges.push_back(edgeInd[i][i+1]);
				if(ans.find(edgeInd[i][i+1]) != ans.end()) trCount++;
			}
			for(int i= ((x>m) ? m+1 : m) ; i<N-1; i++){
				edges.push_back(edgeInd[i][i+1]);
				if(ans.find(edgeInd[i][i+1]) != ans.end()) trCount++;
			}
			for(int i=l; i<=m; i++){
				if(i==x) continue;
				edges.push_back(edgeInd[i][x]);
				if(ans.find(edgeInd[i][x]) != ans.end()) trCount++;
			}
			
			assert(edges.size()==N-1);

			int count = count_common_roads(edges) - trCount;
			// cout<<l<<" "<<r<<" "<<m<<" "<<count<<endl;
			if(count >0) r=m;
			else l=m+1;
		}
		// cout<<l<<endl;

		ans.insert(edgeInd[l][x]);
		deg[x]--;
		deg[l]--;
		if(deg[l]==1) s.push(l);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n;
	assert(u.size() == (n*(n-1))/2);

	if(n==2){
		ve<int> res = {0};
		return res;
	}

	for(int i=0; i < u.size(); i++){
		edgeInd[u[i]][v[i]] = i;
		edgeInd[v[i]][u[i]] = i;
	}

	//initial tree will be the line from 0 to n.
	initTree();

	for(int i=0; i<N; i++) calcDeg(i);

	solve();

	ve<int> res;
	for(int i:ans) res.push_back(i);
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'void solve()':
simurgh.cpp:63:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  while(ans.size()<N-1){
      |        ~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:3:
simurgh.cpp:88:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |    assert(edges.size()==N-1);
      |           ~~~~~~~~~~~~^~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:106:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  assert(u.size() == (n*(n-1))/2);
      |         ~~~~~~~~~^~~~~~~~~~~~~~
simurgh.cpp:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i=0; i < u.size(); i++){
      |               ~~^~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30