oj.uz

Submission #500157

# Submission time Handle Problem Language Result Execution time Memory
500157 2021-12-30T11:57:33 Z benson1029 Stations (IOI20_stations) C++14
0 / 100
 887 ms 636 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; i++) edg[i].clear();
	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);
	tmp.clear();
	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:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0; i<c.size(); i++) if(c[i]>=t) return c[i];
      |                ~^~~~~~~~~
stations.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=0; i<c.size()-1; i++) if(c[i]>=t) return c[i];
      |                ~^~~~~~~~~~~
stations.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
      |                ~^~~~~~~~~
stations.cpp:55:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
      |                                    ~^~~~~~~~~~~~
stations.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 504 KB Output is correct
2 Correct 636 ms 492 KB Output is correct
3 Incorrect 628 ms 516 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

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