Submission #305967

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305967	2020-09-24T07:54:35 Z	p_b_p_b	Stations (IOI20_stations)	C++14	100 / 100	1142 ms	1048 KB

stations

#include<bits/stdc++.h>
#ifndef NTFOrz
#include "stations.h"
#endif
clock_t __t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 2333
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cout<<(clock()-__t)/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

namespace Build
{
	int n;
	struct hh{int t,nxt;}edge[sz<<1];
	int head[sz],ecnt;
	void make_edge(int f,int t)
	{
		edge[++ecnt]=(hh){t,head[f]};
		head[f]=ecnt;
		edge[++ecnt]=(hh){f,head[t]};
		head[t]=ecnt;
	}
	void clear(){rep(i,0,n-1) head[i]=0;ecnt=0;}
	
	int id[sz],cc;
	#define v edge[i].t
	void dfs(int x,int fa,int p)
	{
		if (p) id[x]=++cc;
		go(x) if (v!=fa) dfs(v,x,p^1);
		if (!p) id[x]=++cc;
	}
	#undef v
	vector<int> work()
	{
		cc=0;
		dfs(0,-1,1);
		vector<int>res; rep(i,0,n-1) res.push_back(id[i]);
		return res;
	}
}

vector<int> label(int n,int K,vector<int>u,vector<int>v)
{
	Build::clear();
	Build::n=n; rep(i,0,n-2) Build::make_edge(u[i],v[i]);
	return Build::work();
}

int find_next_station(int s,int t,vector<int>V)
{
	if (s<V[0])
	{
		if (t<s) return V.back();
		rep(i,0,(int)V.size()-2) if (t<=V[i]) return V[i];
		return V.back();
	}
	if (t>s) return V[0];
	drep(i,(int)V.size()-1,1) if (t>=V[i]) return V[i];
	return V[0];
}

#ifdef NTFOrz

//#include "stations.h"
#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>

static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main() {file();
	assert(scanf("%d", &r) == 1);
	for (int tc = 0; tc < r; tc++) {
		assert(scanf("%d%d", &n, &k) == 2);
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++) {
			assert(scanf("%d%d", &u[i], &v[i]) == 2);
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n) {
			printf("Number of labels not equal to %d\n", n);
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++) {
			if (labels[i] < 0 || labels[i] > k) {
				printf("Label not in range 0 to %d\n", k);
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				printf("Labels not unique\n");
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label) {
				max_label = labels[i];
			}
		}
		assert(scanf("%d", &q) == 1);
		for (int i = 0; i < q; i++) {
			assert(scanf("%d%d%d", &s, &t, &w) == 3);
			c.clear();
			for (int v : adjlist[s]) {
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer)) {
				printf("Label %d returned by find_next_station not found in c\n", answer);
				exit(0);
			}
			answers.push_back(reverse_labels[answer]);
		}
	}
	printf("%d\n", max_label);
	for (int index : answers) {
		printf("%d\n", index);
	}
	exit(0);
}

#endif

Compilation message

stations.cpp: In function 'void my_std::print(int)':
stations.cpp:36:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   36 |   if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
      |   ^~
stations.cpp:36:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   36 |   if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
      |                     ^~
stations.cpp:38:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   38 |   while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
      |   ^~~~~
stations.cpp:38:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   38 |   while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
      |                                       ^~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	527 ms	768 KB	Output is correct
2	Correct	469 ms	772 KB	Output is correct
3	Correct	996 ms	768 KB	Output is correct
4	Correct	823 ms	780 KB	Output is correct
5	Correct	694 ms	772 KB	Output is correct
6	Correct	439 ms	1008 KB	Output is correct
7	Correct	434 ms	788 KB	Output is correct
8	Correct	3 ms	896 KB	Output is correct
9	Correct	4 ms	768 KB	Output is correct
10	Correct	2 ms	876 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	464 ms	820 KB	Output is correct
2	Correct	556 ms	768 KB	Output is correct
3	Correct	951 ms	768 KB	Output is correct
4	Correct	695 ms	768 KB	Output is correct
5	Correct	609 ms	768 KB	Output is correct
6	Correct	550 ms	832 KB	Output is correct

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	702 ms	760 KB	Output is correct
2	Correct	593 ms	776 KB	Output is correct
3	Correct	1047 ms	876 KB	Output is correct
4	Correct	660 ms	876 KB	Output is correct
5	Correct	657 ms	1008 KB	Output is correct
6	Correct	461 ms	888 KB	Output is correct
7	Correct	539 ms	1048 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	4 ms	768 KB	Output is correct
10	Correct	1 ms	768 KB	Output is correct
11	Correct	635 ms	768 KB	Output is correct
12	Correct	515 ms	780 KB	Output is correct
13	Correct	521 ms	780 KB	Output is correct
14	Correct	452 ms	836 KB	Output is correct
15	Correct	51 ms	1000 KB	Output is correct
16	Correct	74 ms	768 KB	Output is correct
17	Correct	124 ms	1024 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1142 ms	868 KB	Output is correct
2	Correct	684 ms	880 KB	Output is correct
3	Correct	662 ms	880 KB	Output is correct
4	Correct	3 ms	876 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	2 ms	880 KB	Output is correct
7	Correct	634 ms	876 KB	Output is correct
8	Correct	881 ms	768 KB	Output is correct
9	Correct	678 ms	768 KB	Output is correct
10	Correct	645 ms	768 KB	Output is correct
11	Correct	7 ms	768 KB	Output is correct
12	Correct	7 ms	768 KB	Output is correct
13	Correct	4 ms	884 KB	Output is correct
14	Correct	4 ms	884 KB	Output is correct
15	Correct	2 ms	880 KB	Output is correct
16	Correct	557 ms	876 KB	Output is correct
17	Correct	602 ms	872 KB	Output is correct
18	Correct	508 ms	768 KB	Output is correct
19	Correct	549 ms	780 KB	Output is correct
20	Correct	503 ms	880 KB	Output is correct

Subtask #5

61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	549 ms	772 KB	Output is correct
2	Correct	473 ms	780 KB	Output is correct
3	Correct	920 ms	768 KB	Output is correct
4	Correct	732 ms	760 KB	Output is correct
5	Correct	715 ms	768 KB	Output is correct
6	Correct	494 ms	772 KB	Output is correct
7	Correct	450 ms	800 KB	Output is correct
8	Correct	3 ms	880 KB	Output is correct
9	Correct	5 ms	768 KB	Output is correct
10	Correct	2 ms	884 KB	Output is correct
11	Correct	517 ms	768 KB	Output is correct
12	Correct	601 ms	820 KB	Output is correct
13	Correct	983 ms	880 KB	Output is correct
14	Correct	657 ms	880 KB	Output is correct
15	Correct	579 ms	1024 KB	Output is correct
16	Correct	452 ms	768 KB	Output is correct
17	Correct	624 ms	780 KB	Output is correct
18	Correct	520 ms	792 KB	Output is correct
19	Correct	569 ms	1016 KB	Output is correct
20	Correct	559 ms	832 KB	Output is correct
21	Correct	76 ms	880 KB	Output is correct
22	Correct	98 ms	856 KB	Output is correct
23	Correct	135 ms	840 KB	Output is correct
24	Correct	6 ms	768 KB	Output is correct
25	Correct	5 ms	768 KB	Output is correct
26	Correct	4 ms	768 KB	Output is correct
27	Correct	3 ms	768 KB	Output is correct
28	Correct	2 ms	768 KB	Output is correct
29	Correct	506 ms	876 KB	Output is correct
30	Correct	559 ms	768 KB	Output is correct
31	Correct	723 ms	688 KB	Output is correct
32	Correct	717 ms	1024 KB	Output is correct
33	Correct	622 ms	1008 KB	Output is correct
34	Correct	321 ms	784 KB	Output is correct
35	Correct	453 ms	1024 KB	Output is correct
36	Correct	457 ms	876 KB	Output is correct
37	Correct	465 ms	816 KB	Output is correct
38	Correct	456 ms	940 KB	Output is correct
39	Correct	464 ms	812 KB	Output is correct
40	Correct	472 ms	768 KB	Output is correct
41	Correct	468 ms	824 KB	Output is correct
42	Correct	60 ms	848 KB	Output is correct
43	Correct	108 ms	964 KB	Output is correct
44	Correct	143 ms	844 KB	Output is correct
45	Correct	173 ms	768 KB	Output is correct
46	Correct	320 ms	828 KB	Output is correct
47	Correct	328 ms	804 KB	Output is correct
48	Correct	73 ms	768 KB	Output is correct
49	Correct	73 ms	828 KB	Output is correct