Submission #1062401

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1062401	2024-08-17T06:06:29 Z	nightfal	Stations (IOI20_stations)	C++17	13 / 100	644 ms	944 KB

stations

#include <vector>
#include <iostream>
using namespace std;

template <typename T> void print(T elem) {cout << elem << " ";}
template <typename T> void print(vector<T> &v) {for(auto elem: v) print(elem); cout << endl;}
template <typename T> void print(vector<vector<T>> &v) {for(auto elem: v) print(elem); cout << endl;}

void makeG(vector<vector<int>> &g, vector<int> &u, vector<int> &v) {
	for(int i=0; i<u.size(); i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
}
int labelSubDecision(int n, int k, vector<vector<int>> &g, vector<int> &u, vector<int> &v) {
	int cnt = 0;
	for(int i=0; i<n; i++)
		if (g[i].size()>2) cnt++;
	if (cnt==0) return 1;

	bool subtask2 = true;
	for(int i=0; i<u.size(); i++)
		if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1)) subtask2= false;
	if (subtask2) return 2;

	if (cnt==1) return 3;
}
void labelLine(int cnt, int node, vector<vector<int>> &g, vector<int> &labels) {
	while(labels[node]==-1) {
		labels[node] = cnt++;
		for(int elem: g[node])
			if (labels[elem]==-1) node = elem;
	}
	return;
}
void labelSub1(int n, vector<vector<int>> &g, vector<int> &labels) {
	int node = 0;
	for(int i=0; i<n; i++)
		if(g[i].size()==1) node=i;

	labelLine(0,node,g,labels);
	return;
}
void labelSub2(int n, vector<int> &labels) {
	for(int i=0; i<n; i++)
		labels[i] = i+1;
	return;
}
void labelSub3(int n, int k, vector<vector<int>> &g, vector<int> &labels) {
	int root = 0;
	for(int i=0; i<n; i++)
		if(g[i].size() > 2) {root = i; break;}
	labels[root] = 1'000;
	for(int i=0; i<g[root].size(); i++)
		labelLine((i+1)*1'000+1,i,g,labels);
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> g(n);
	makeG(g,u,v);
	// print(g);
	int subtask = labelSubDecision(n,k,g,u,v);
	vector<int> labels(n,-1);
	switch(subtask) {
		case 1: labelSub1(n,g,labels); return labels;
		case 2: labelSub2(n,labels); return labels;
		case 3: labelSub3(n,k,g,labels); return labels;
	}
}
int findSubDecision(int s, int t, vector<int> &c) {
	if (s >= 1'000 && t >= 1'000) return 3;
	for(int i=0; i<c.size(); i++)
		if (c[i] < s-1 || c[i] > s+1) return 2;
	return 1;
}
int findSub1(int s, int t, vector<int> &c) {
	if (c.size()==1) return c[0];
	else return t<s? c[0]:c[1];
}
bool ancestor(int a, int b) {
	if (a==0) return true;
	while(b!=0) { if(a==b) return true; else b >>= 1; }
	return false;
}
int findSub2(int s, int t, vector<int> &c) {
	for(int i=c.size()-1; i>=0; i--)
		if(ancestor(c[i],t)) return c[i];
	return c[0];
}
int findSub3(int s, int t, vector<int> &c) {
	if (s==1'000) {
		for(int elem: c)
			if(t/1000==elem/1000) return elem;
	}
	else if (s/1000 == t/1000) {
		if(s < t) {
			for(int elem: c)
				if(elem > s) return elem;
		}
		else {
			for(int elem: c)
				if(elem < s) return elem;
		}
	}
	else {
			for(int elem: c)
				if(elem < s) return elem;
	}
}
int find_next_station(int s, int t, std::vector<int> c) {
	int subtask = findSubDecision(s,t,c);
	switch(subtask) {
		case 1: return findSub1(s,t,c);
		case 2: return findSub2(s,t,c);
		case 3: return findSub3(s,t,c);
	}
	return c[0];
}

Compilation message

stations.cpp: In function 'void makeG(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i=0; i<u.size(); i++) {
      |               ~^~~~~~~~~
stations.cpp: In function 'int labelSubDecision(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<u.size(); i++)
      |               ~^~~~~~~~~
stations.cpp:23:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   23 |   if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1)) subtask2= false;
stations.cpp: In function 'void labelSub3(int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0; i<g[root].size(); i++)
      |               ~^~~~~~~~~~~~~~~
stations.cpp: In function 'int findSubDecision(int, int, std::vector<int>&)':
stations.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0; i<c.size(); i++)
      |               ~^~~~~~~~~
stations.cpp: In function 'int labelSubDecision(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
stations.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:58:25: warning: control reaches end of non-void function [-Wreturn-type]
   58 |  vector<vector<int>> g(n);
      |                         ^
stations.cpp: In function 'int findSub3(int, int, std::vector<int>&)':
stations.cpp:108:1: warning: control reaches end of non-void function [-Wreturn-type]
  108 | }
      | ^

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	363 ms	684 KB	Output is correct
2	Correct	283 ms	684 KB	Output is correct
3	Correct	577 ms	684 KB	Output is correct
4	Correct	454 ms	944 KB	Output is correct
5	Correct	373 ms	684 KB	Output is correct
6	Correct	321 ms	684 KB	Output is correct
7	Correct	292 ms	684 KB	Output is correct
8	Correct	1 ms	764 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	0 ms	768 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	684 KB	Output is correct
2	Correct	376 ms	684 KB	Output is correct
3	Correct	617 ms	684 KB	Output is correct
4	Correct	487 ms	684 KB	Output is correct
5	Correct	384 ms	684 KB	Output is correct
6	Correct	326 ms	684 KB	Output is correct

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	324 ms	684 KB	Output is correct
2	Correct	309 ms	688 KB	Output is correct
3	Correct	582 ms	684 KB	Output is correct
4	Correct	450 ms	684 KB	Output is correct
5	Correct	390 ms	684 KB	Output is correct
6	Correct	288 ms	684 KB	Output is correct
7	Correct	296 ms	684 KB	Output is correct
8	Correct	1 ms	776 KB	Output is correct
9	Correct	1 ms	768 KB	Output is correct
10	Correct	1 ms	764 KB	Output is correct
11	Incorrect	1 ms	344 KB	Invalid labels (values out of range). scenario=1, k=1000000, vertex=3, label=-1
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	644 ms	684 KB	Output is correct
2	Correct	482 ms	680 KB	Output is correct
3	Correct	404 ms	684 KB	Output is correct
4	Correct	2 ms	768 KB	Output is correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	1 ms	768 KB	Output is correct
7	Incorrect	0 ms	344 KB	Invalid labels (values out of range). scenario=0, k=1000000000, vertex=3, label=-1
8	Halted	0 ms	0 KB	-

Subtask #5

0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	378 ms	684 KB	Output is correct
2	Correct	351 ms	684 KB	Output is correct
3	Correct	635 ms	684 KB	Output is correct
4	Correct	432 ms	712 KB	Output is correct
5	Correct	444 ms	684 KB	Output is correct
6	Correct	345 ms	684 KB	Output is correct
7	Correct	297 ms	684 KB	Output is correct
8	Correct	1 ms	776 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	0 ms	772 KB	Output is correct
11	Correct	286 ms	684 KB	Output is correct
12	Correct	340 ms	684 KB	Output is correct
13	Correct	633 ms	684 KB	Output is correct
14	Correct	484 ms	684 KB	Output is correct
15	Correct	418 ms	684 KB	Output is correct
16	Correct	309 ms	684 KB	Output is correct
17	Incorrect	1 ms	344 KB	Invalid labels (values out of range). scenario=0, k=1000000000, vertex=3, label=-1
18	Halted	0 ms	0 KB	-