Submission #604772

#	Time	Username	Problem	Language	Result	Execution time	Memory
604772		gagik_2007	Stations (IOI20_stations)	C++17	16 / 100	957 ms	768 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];
vector<int>gic[1007];

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> lbl(n);
	for (int i = 0; i < n - 1; i++) {
		cnt[v[i]]++;
		cnt[u[i]]++;
		g[v[i]].push_back(u[i]);
		g[u[i]].push_back(v[i]);
	}
	ll qan = 0;
	int ind = 0;
	int curgic = 1;
	for (int i = 0; i < n; i++) {
		if (cnt[i] > 2) {
			ind = i;
			lbl[i] = 0;
			break;
		}
	}
	for (int j = 0; j < g[ind].size(); j++) {
		gic[curgic].push_back(g[ind][j]);
		curgic++;
	}
	qan = cnt[ind];
	//cout << qan << " " << curgic << endl;
	for (int cur = 1; cur < curgic; cur++) {
		int lst = ind;
		int ci = gic[cur][0];
		int cv = cur * 1000;
		while (cnt[ci] != 1) {
			lbl[ci] = cv;
			cv += 1;
			if (g[ci][0] == lst) {
				lst = ci;
				ci = g[ci][1];
			}
			else {
				lst = ci;
				ci = g[ci][0];
			}
		}
		lbl[ci] = cv;
	}
	/*for (int i = 0; i < n; i++) {
		cout << lbl[i] << " ";
	}
	cout << endl;*/
	for (int i = 0; i < n; i++) {
		g[i].clear();
		gic[i].clear();
		cnt[i] = 0;
	}
	gic[n].clear();
	return lbl;
}

int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1)return c[0];
	if (s == 0) {
		int ht = t / 1000;
		int nt = t % 1000;
		for (int v : c) {
			int hv = v / 1000;
			if (ht == hv)return v;
		}
	}
	else {
		int hs = s / 1000;
		int ns = s % 1000;
		int ht = t / 1000;
		int nt = t % 1000;
		if (hs != ht) {
			if (ns == 0)return 0;
			else return s - 1;
		}
		else {
			if (ns > nt) {
				return s - 1;
			}
			else return s + 1;
		}
	}
}

/*
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 
*/

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int j = 0; j < g[ind].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~
stations.cpp:40:5: warning: variable 'qan' set but not used [-Wunused-but-set-variable]
   40 |  ll qan = 0;
      |     ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:91:7: warning: unused variable 'nt' [-Wunused-variable]
   91 |   int nt = t % 1000;
      |       ^~
stations.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
  113 | }
      | ^

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