Submission #377915

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
377915	2021-03-15T14:22:15 Z	Thistle	Stations (IOI20_stations)	C++14	0 / 100	888 ms	928 KB

stations

#include "stations.h"
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define pb push_back
#define vec vector
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define siz(a) ll((a).size())


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {

	vec<vi>e(n);
	rep(i,n-1){
		e[u[i]].pb(v[i]);
		e[v[i]].pb(u[i]);
	}
	vi in(n),out(n),dpt(n,0);
	int idx=0;
	auto dfs=[&](int x,int p,int d,auto& dfs)->void{
		in[x]=idx++;
		dpt[x]=d;
		for(auto g:e[x]){
			if(g==p) continue;
			dfs(g,x,d+1,dfs);
		}
		out[x]=idx++;
	};
	dfs(0,-1,0,dfs);
	std::vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		if(!(dpt[i]&1)){
			labels[i]=in[i];
		}
		else{
			labels[i]=out[i];
		}
	}
	vec<int>tmp=labels;
	sort(all(tmp));
	tmp.erase(unique(all(tmp)),tmp.end());
	for(auto& g:labels){
		g=lower_bound(all(tmp),g)-tmp.begin();
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int mx=-10000,mn=10000;
	for(auto g:c){
		mx=max(mx,g);
		mn=min(mn,g);
	}
	//subete no kodomo no kukan wo motomeru
	vec<H>itv(siz(c),H{-1,-1});
	int root=-1;
	if(mx<s){
		//saishou no yatu ga ne
		root=mn;
		sort(all(c));
		c.erase(c.begin());
		//kore de ne igai ni natta
		rep(i,siz(c)){
			itv[i].fs=c[i];
			if(i<siz(c)-1) itv[i].sc=c[i+1];
			else itv[i].sc=s;
		}
	}
	else{
		if(s!=0) root=mx;
		sort(all(c));
		if(c.back()==root) c.erase(prev(c.end()));
		rep(i,siz(c)){
			if(i==0) itv[i].fs=s+1;
			else itv[i].fs=c[i-1]+1;
			itv[i].sc=c[i]+1;
		}
	}
	rep(i,siz(c)){
		if(itv[i].fs<=t&&t<=itv[i].sc){
			return c[i];
		}
	}
	return root;
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
stations.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
stations.cpp:22:2: note: in expansion of macro 'rep'
   22 |  rep(i,n-1){
      |  ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
stations.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
stations.cpp:71:3: note: in expansion of macro 'rep'
   71 |   rep(i,siz(c)){
      |   ^~~
stations.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
stations.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
stations.cpp:81:3: note: in expansion of macro 'rep'
   81 |   rep(i,siz(c)){
      |   ^~~
stations.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
stations.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
stations.cpp:87:2: note: in expansion of macro 'rep'
   87 |  rep(i,siz(c)){
      |  ^~~

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	512 ms	928 KB	Wrong query response.
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	463 ms	876 KB	Wrong query response.
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	548 ms	888 KB	Wrong query response.
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	888 ms	884 KB	Output is correct
2	Incorrect	753 ms	756 KB	Wrong query response.
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	527 ms	884 KB	Wrong query response.
2	Halted	0 ms	0 KB	-