oj.uz

답안 #500151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500151 2021-12-30T11:50:00 Z benson1029 기지국 (IOI20_stations) C++14
0 / 100
 3000 ms 2097156 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

int timer = 0;
int st[1005], ed[1005], dep[1005];
vector<int> edg[1005];
vector<int> ans;
vector< pair<int,int> > tmp;

void dfs(int x, int p) {
	if(x==0) dep[x] = 0;
	else dep[x] = dep[p]+1;
	st[x] = ++timer;
	for(int i:edg[x]) {
		if(i!=p) {
			dfs(i, x);
		}
	}
	ed[x] = ++timer;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for(int i=0; i<n-1; i++) {
		edg[u[i]].push_back(v[i]);
		edg[v[i]].push_back(u[i]);
	}
	dfs(0, -1);
	ans.resize(n);
	for(int i=0; i<n; i++) {
		if(dep[i]%2==0) ans[i] = st[i];
		else ans[i] = ed[i];
		tmp.push_back({ans[i], i});
	}
	sort(tmp.begin(), tmp.end());
	for(int i=0; i<n; i++) {
		ans[tmp[i].second] = i;
	}
	return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(s == 0) {
		sort(c.begin(), c.end());
		for(int i=0; i<c.size(); i++) if(c[i]>=t) return c[i];
	} else if(c[0] > s) { // s uses start time
		sort(c.begin(), c.end());
		if(t < s || t >= c[c.size()-1]) return c[c.size()-1];
		for(int i=0; i<c.size()-1; i++) if(c[i]>=t) return c[i];
	} else if(c[0] < s) { // s uses end time
		sort(c.begin(), c.end());
		if(t <= c[0] || t > s) return c[0];
		for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=0; i<c.size(); i++) if(c[i]>=t) return c[i];
      |                ~^~~~~~~~~
stations.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0; i<c.size()-1; i++) if(c[i]>=t) return c[i];
      |                ~^~~~~~~~~~~
stations.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
      |                ~^~~~~~~~~
stations.cpp:53:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
      |                                    ~^~~~~~~~~~~~
stations.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1433 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3053 ms 464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1433 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 856 ms 512 KB Output is correct
2 Runtime error 1051 ms 2097156 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2662 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -