oj.uz

답안 #432938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432938 2021-06-18T15:26:18 Z lior5654 기지국 (IOI20_stations) C++17
0 / 100
 963 ms 768 KB 
#include <bits/stdc++.h>

using namespace std;


typedef long long int ll;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(c) (c.begin()), (c.end())
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define csz(c) ((int)c.size())

#include "stations.h"


const int maxn = 1e3 + 5;


vi g[maxn];
int st[maxn]; int en[maxn]; int d[maxn]; int dt = -1;

void dfs(int c, int p=-1, int dd=0) {
	st[c] = ++dt; 
    d[c] = dd;
	for(auto e  : g[c]) {
		if(e!=p) {
			dfs(e, c, dd+1);
		}
	}
	en[c] = ++dt;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {

	rep(i, n-1) {
		g[u[i]].pb(v[i]); g[v[i]].pb(u[i]);
	}
	dfs(0);
	vi res(n);
	rep(i, n) {
        if(d[i]%2) {
            res[i] = en[i];
        } else {
            res[i] = st[i];
        }
	}
	/*cout << "debug" << endl;
	rep(i, n) {
		cout << st[i] << ' '<< en[i] << endl;
	}
	for(auto e : res) {
		cout << e << ' ';
	}
	cout << endl;
	*/
	rep(i, n) {
		g[i].clear(); st[i] = 0; en[i] = 0; d[i] = 0;
	}
	dt = -1;
	return res;
}


const int base = 2004;


int find_next_station_bad(int s, int t, std::vector<int> c) {
	int s_st = s % base;
	int t_st = t % base;
	int s_en = s / base;
	int t_en = t / base;
	vi childs;
	int best = 0;
	for(int i = 1; i < c.size(); ++i) {
		if(c[i] % base < c[best] % base) {
			best = i;
		}
	}
	int papa_label = c[best];
	int papa_st = papa_label % base;
	int papa_en = papa_label / base;
	if(papa_st < s_st) { // there's a papa
		for(auto e : c) {
			if(e != papa_label) {
				childs.pb(e);
			}
		}
	} else { // there's no papa
		for(auto e : c) {
			childs.pb(e);
		}
	}
	if(papa_st < s_st) {
		if(t_st > s_en || t_st < s_st) {
			return papa_label;
		}
	}
	sort(all(childs), [&](int xx, int yy) {
		return xx % base < yy % base;
	});
	// find the first child whose end time is bigger than or equal to t's start time
	for(int i = 0; i < childs.size(); ++i) {
		if(childs[i] / base >= t_st) return childs[i];
	}
	
	assert(false);
}



int find_next_station(int s, int t, std::vector<int> c) {
	if(c.size() == 1) return c[0];
    vi ac; int as; int at;
    
    map<int, int> lconv;
    if(s < *min_element(all(c))) { // lemma: this is true if and only if I am a starting time
        sort(all(c));
        int next_st = s + 1;
        for(int i = 0; i < csz(c) - 1; ++i) {
            lconv[base * c[i] + next_st] = c[i];
            if(next_st <= t && t <= c[i]) {
                return c[i];
            }
            return c[csz(c) - 1];
            ac.pb(base * c[i] + next_st);
            next_st = c[i] + 1;
        }

        // maybe if s is the root of the tree this is an issue
        if(s == 0) {
            lconv[base * c[csz(c)-1] + 1] = c[csz(c)-1];
            ac.pb(base * c[csz(c)-1] + 1); // let it be 0 or some shit
        } else {
            lconv[base * c[csz(c)-1] + 0] = c[csz(c)-1];
            ac.pb(base * c[csz(c)-1] + 0); // let it be 0 or some shit
        }
        at = (base * t + t); // maybe this is an issue?
        as = base * next_st + s;

    } else { // I claim I am an ending time and all other people are starting times
        sort(all(c));
        reverse(all(c));
        int next_en = s - 1;
        for(int i = 0; i < csz(c) - 1; ++i) {
            lconv[base * next_en + c[i]] = c[i];
            ac.pb(base * next_en + c[i]);
            if(t >= c[i] && t <= next_en) return c[i];
            next_en = c[i] - 1;
        }
        return c[csz(c) - 1];

        lconv[c[csz(c)-1] + base * 2002] = c[csz(c)-1];
        ac.pb(c[csz(c)-1] + base * 2002); // let it be 0 or some shit
        at = (base * t + t); // maybe this is an issue?
        as = base * s + next_en;
    }

    return lconv[find_next_station_bad(as, at, ac)];
}

Compilation message

stations.cpp: In function 'int find_next_station_bad(int, int, std::vector<int>)':
stations.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i = 1; i < c.size(); ++i) {
      |                 ~~^~~~~~~~~~
stations.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(int i = 0; i < childs.size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~~
stations.cpp:83:6: warning: unused variable 't_en' [-Wunused-variable]
   83 |  int t_en = t / base;
      |      ^~~~
stations.cpp:93:6: warning: unused variable 'papa_en' [-Wunused-variable]
   93 |  int papa_en = papa_label / base;
      |      ^~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 448 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 448 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 551 ms 624 KB Output is correct
2 Correct 496 ms 744 KB Output is correct
3 Correct 963 ms 508 KB Output is correct
4 Correct 687 ms 508 KB Output is correct
5 Correct 694 ms 556 KB Output is correct
6 Correct 428 ms 624 KB Output is correct
7 Correct 530 ms 528 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Incorrect 526 ms 504 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 850 ms 528 KB Output is correct
2 Correct 650 ms 580 KB Output is correct
3 Correct 594 ms 444 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 7 ms 608 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 545 ms 528 KB Output is correct
8 Correct 860 ms 528 KB Output is correct
9 Correct 654 ms 400 KB Output is correct
10 Correct 622 ms 516 KB Output is correct
11 Incorrect 6 ms 472 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 560 ms 768 KB Partially correct
2 Partially correct 466 ms 620 KB Partially correct
3 Correct 827 ms 400 KB Output is correct
4 Correct 680 ms 528 KB Output is correct
5 Correct 641 ms 520 KB Output is correct
6 Partially correct 464 ms 644 KB Partially correct
7 Partially correct 468 ms 516 KB Partially correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Incorrect 430 ms 508 KB Wrong query response.
12 Halted 0 ms 0 KB -