제출 #432919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432919		lior5654	기지국 (IOI20_stations)	C++17	0 / 100	1012 ms	624 KiB

stations

#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 = 2001;


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) {
	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];
            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]);
            next_en = c[i] - 1;
        }


        lconv[c[csz(c)-1] + base * 2000] = c[csz(c)-1];
        ac.pb(c[csz(c)-1] + base * 2000); // 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)];
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61