oj.uz

답안 #305967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305967 2020-09-24T07:54:35 Z p_b_p_b 기지국 (IOI20_stations) C++14
100 / 100
 1142 ms 1048 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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