Submission #500886

#	Time	Username	Problem	Language	Result	Execution time	Memory
500886		keta_tsimakuridze	Speedrun (RMI21_speedrun)	C++14	48 / 100	351 ms	868 KiB

speedrun

#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, f[N], cnt, deg[N], l[N] ;
vector<int> V[N];
/*
#include <iostream>
#include <map>
#include <set>
using namespace std;

static map<int, map<int, bool> > mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int> > neighbours;

void setHintLen(int l) {
    if (length_set) {
        cerr << "Cannot call setHintLen twice" << endl;
        exit(0);
    }
    length = l;
    length_set = true;
}

void setHint(int i, int j, bool b) {
    if (!length_set) {
        cerr << "Must call setHintLen before setHint" << endl;
        exit(0);
    }
    mp[i][j] = b;
}

int getLength() { return length; }

bool getHint(int j) { return mp[current_node][j]; }

bool goTo(int x) {
    if (neighbours[current_node].find(x) == neighbours[current_node].end()) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        cout << current_node <<" is current" << endl;
        return true;
    }
} */
void add(int a,int b) {
	if(deg[a] == 1) {
		for(int j = 1; j <= 10; j++) {
			if(b & (1  << (j - 1))) setHint(a, j, 1);
		}		
		return;
	}
	for(int j = 11; j <= 20; j++) {
		if(b & (1  << (j - 11))) setHint(a, j, 1);
	}		
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	if(subtask == 1) {
		setHintLen(N);
		for(int i = 1; i < N; i++) {
			setHint(A[i], B[i], 1);
			setHint(B[i], A[i], 1);
		}
	}
	else if(subtask == 2) {
		setHintLen(20);
		int x = -1;
		for(int i = 1; i < N; i++) {
			deg[A[i]]++; deg[B[i]]++;
			if(deg[A[i]] == N - 2) x = A[i];
			if(deg[B[i]] == N - 2) x = A[i];
		}
		for(int i = 1; i <= N; i++) {
			if(i == x) continue;
			for(int j = 1; j <= 10; j++) {
				if((1 << (j - 1)) & x) setHint(i, j, 1);
			}
		}
	}
	else if(subtask == 3) {
		setHintLen(20);
		for(int i = 1; i < N; i++) {
			deg[A[i]]++; deg[B[i]]++;
			add(A[i], B[i]);
			add(B[i], A[i]);
		}
	}
	else if(subtask == 4) {
		setHintLen(311);
		vector<int> V[N + 5];
		for(int i = 1; i < N; i++) {
			V[A[i]].push_back(B[i]);
			V[B[i]].push_back(A[i]);
		} 
		for(int i = 1; i <= N; i++) {
			if(V[i].size() <= 31) {
				int cur = 1;
				for(int j = 0; j< V[i].size(); j++) {
					for(int k = 1;k <= 10; k++) {
						if(V[i][j] & (1 << ( k - 1))) setHint(i, cur, 1);
				
						cur++;
					}
				}
			}
			else setHint(i, 311, 1);
		}
	}
}
void dfs2(int u) {
	int x = 0; 
	for(int j = 1; j <= 10; j++) x += (1 << (j - 1)) * getHint(j);
	if(!x) {
		for(int i = 1; i <= n; i++) {
			if(i == u  || f[i]) continue;
			f[i] = 1; cnt++;
			assert(goTo(i));
			dfs2(i);
		}
	}
	else if(cnt == n) return;
	else goTo(x), dfs2(x);
}
void dfs(int u,int subtask, int par) {  
	if(subtask == 1){
		for(int i = 1; i <= n; i++) {
			if(getHint(i)) V[u].push_back(i);
		}		
	}
	else{
		int x = 0;
		for(int i = 1; i <= 10; i++) {
			x += getHint(i) * ((1 << (i - 1)));
		}
		V[u].push_back(x);
		x = 0;
		for(int i = 11; i <= 20; i++) {
			x += getHint(i) * ((1 << (i - 11)));
		}
		if(x) V[u].push_back(x);
	}

	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i] == par) continue;
		goTo(V[u][i]);
		dfs(V[u][i], subtask, u);
	}
	if(par != - 1)goTo(par);
}
void dfs4(int u, int par) {
	if(!getHint(311)) {
		for(int i = 1; i <= 31; i++) {
			int x = 0; 
			for(int j = 1; j <=  10; j++) {
				if(getHint((i - 1) * 10 + j)) x += 1 << (j - 1);
			}
			if(x) V[u].push_back(x);
		}
		for(int i = 0; i < V[u].size(); i++) {
			if(V[u][i] != par) cnt++, goTo(V[u][i]),   dfs4(V[u][i], u);
		}
	} 
	else {
		int x = l[u] + 1;
		for(int i = x; i <= n; i++) {
			l[u]++;
			if(i == u) continue;
			int t = goTo(i);
			if(par != i && t) {
				cnt++;
				dfs4(i, u);
			}
		}
	}
	if(par != -1) goTo(par);
}
void speedrun(int subtask, int N, int start) { /* your solution here */
	
	n = N;
	if(subtask == 1) dfs(start, 1, -1);
	if(subtask == 2) {
		dfs2(start);
	}
	else if(subtask == 3) { 
		dfs(start, 3, -1);
	}
	else if(subtask == 4) { cnt = 0;
		dfs4(start, -1);
	}
}
/*
int main() {
    int N;
    cin >> N;

    int a[N], b[N];
    for (int i = 1; i < N; ++i) {
        cin >> a[i] >> b[i];
        neighbours[a[i]].insert(b[i]);
        neighbours[b[i]].insert(a[i]);
    }

    assignHints(4, N, a, b);

    if (!length_set) {
        cerr << "Must call setHintLen at least once" << endl;
        exit(0);
    }

    cin >> current_node;
    viz.insert(current_node);

    speedrun(4, N, current_node);

    if (viz.size() < N) {
        cerr << "Haven't seen all nodes" << endl;
        exit(0);
    }

    cerr << "OK; " << queries << " incorrect goto's" << endl;
    return 0;
} */

Compilation message (stderr)

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int j = 0; j< V[i].size(); j++) {
      |                    ~^~~~~~~~~~~~~
speedrun.cpp: In function 'void dfs(int, int, int)':
speedrun.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
speedrun.cpp: In function 'void dfs4(int, int)':
speedrun.cpp:165:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |   for(int i = 0; i < V[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40