Submission #604712

#	Time	Username	Problem	Language	Result	Execution time	Memory
604712		gagik_2007	Stations (IOI20_stations)	C++17	8 / 100	949 ms	548 KiB

stations

#include "stations.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

ll n;
ll cnt[1007];
vector<int>g[1007];

int get_level(int v) {
	//v++;
	return log2(v);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> lbl(n);
	for (int i = 0; i < n; i++) {
		lbl[i] = i + 1;
	}
	return lbl;
}

bool papa(int s, int t) {
	//cout << "IsPapa: " << s << " " << t << endl;
	if (s == t)return true;
	int ls = get_level(s);
	int lt = get_level(t);
	if (ls >= lt)return false;
	int lvl = lt - ls;
	int vl = (1 << lvl);
	int sk = vl * s;
	int vj = sk + vl - 1;
	//cout << ls << " " << lt << " " << lvl << " " << vl << " " << sk << " " << vj << endl;
	return (t >= sk && t <= vj);
}

int find_next_station(int s, int t, vector<int> c) {
	//cout << "Doing: " << s << " " << t << endl;
	if (c.size() == 1)return c[0]; 
	if (papa(s, t)) {
		if (papa(2 * s, t))return 2 * s;
		else return 2 * s + 1;
	}
	else return s / 2;
}

/*
1
8 1000
0 1
0 2
1 3
1 4
3 5
3 6
5 7
5
7 2 5
2 3 0
6 5 3
7 4 5
6 4 3
1 8 1000 0 1 0 2 1 3 1 4 3 5 3 6 5 7 5 7 2 5 2 3 0 6 5 3 7 4 5 6 4 3
1 8 1000 
0 1 
0 2 
1 3 
1 4 
2 5 
2 6 
3 7 
5 
7 2 3 
1 7 3 
2 5 5 
0 5 2 
5 0 2 
*/

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61