Submission #43792

#	Time	Username	Problem	Language	Result	Execution time	Memory
43792		yusufake	Simurgh (IOI17_simurgh)	C++14	0 / 100	4 ms	4568 KiB

simurgh

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

using namespace std; 

#define _   int v, int tl, int tr, int l, int r, int h
#define tm  (tl + tr >> 1)
#define sol v+v,tl,tm,l,r,h 
#define sag v+v+1,tm+1,tr,l,r,h 

#define mp make_pair 
#define pb push_back 
#define st first 
#define nd second 

typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 1e3 + 3; 

vector < int > v, dfstree;
int T[N],A[N][N],H[N],X,n;

void f(int x, int p){
	H[x] = 1;
	for(int y=0; y<n; y++){
		if(H[y] || A[x][y] == -1) continue;
		f(y,x);
		dfstree.pb(A[x][y]);
	}
}
void g(int x, int p){
	H[x] = 1;
	v.pb(x);
	for(int y=0; y<n; y++){
		if(y == p || A[x][y]==-1) continue;
		if(H[y]){
            if(A[x][y] != -1) continue; 
			int i,j,a,b;
			for(i=0;i<v.size();i++) if(v[i] == y) break;
			bool h=0,h2=0;
			for(j=i;j<v.size()-1; j++){ 
				if(T[ A[ v[j] ][ v[j+1] ] ] == 0)  h=1;  
				if(T[ A[ v[j] ][ v[j+1] ] ] == -1) h2=1;
			}
			if(h==1){
				for(j=i;j<v.size()-1; j++)
					if(T[ A[ v[j] ][ v[j+1] ] ] == -1) 
						T[ A[ v[j] ][ v[j+1] ] ] = 1;
				T[ A[x][y] ] = 1;
				continue;
			}
			if(h2 == 0){
				T[ A[x][y] ] = 0; continue;
			}
			for(j=i;j<v.size()-1; j++){
				a = v[j]; b = v[j+1];
				if(T[ A[a][b] ] == 1) continue;
				vector < int > qry;
				for(i=0;i<dfstree.size();i++) if(dfstree[i] != A[a][b]) qry.pb(dfstree[i]);
				qry.pb(A[x][y]);
				int com = count_common_roads(qry);
				if(com == X)   { T[ A[a][b] ] = 1; T[ A[x][y] ] = 1; }
				if(com == X+1) { T[ A[a][b] ] = 0; T[ A[x][y] ] = 1; }
				if(com == X-1) { T[ A[a][b] ] = 1; T[ A[x][y] ] = 0; }
			}
		}
		else g(y,x);
	}
	v.pop_back();
}

vector<int> find_roads(int a, vector<int> u, vector<int> v) {
	int i;
	memset(A , -1 , sizeof A);
	memset(T , -1 , sizeof T);
	for(i=0;i<v.size();i++) A[ v[i] ][ u[i] ] = A[ u[i] ][ v[i] ] = i;
	n = a;
	f(1,0);
	X = count_common_roads(dfstree);
	g(1,0);
	vector < int > ans;
	for(i=0;i<v.size();i++)
		if(T[i] != 0)
			ans.pb(i);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void g(int, int)':
simurgh.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++) if(v[i] == y) break;
             ^
simurgh.cpp:42:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=i;j<v.size()-1; j++){ 
             ^
simurgh.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=i;j<v.size()-1; j++)
              ^
simurgh.cpp:56:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=i;j<v.size()-1; j++){
             ^
simurgh.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<dfstree.size();i++) if(dfstree[i] != A[a][b]) qry.pb(dfstree[i]);
              ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:77:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v.size();i++) A[ v[i] ][ u[i] ] = A[ u[i] ][ v[i] ] = i;
           ^
simurgh.cpp:83:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v.size();i++)
           ^

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