結果
| 問題 | No.1833 Subway Planning |
| ユーザー |
 shotoyoo
|
| 提出日時 | 2022-02-04 23:24:30 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,406 bytes |
| コンパイル時間 | 2,591 ms |
| コンパイル使用メモリ | 219,712 KB |
| 実行使用メモリ | 20,668 KB |
| 最終ジャッジ日時 | 2023-09-02 05:57:31 |
| 合計ジャッジ時間 | 45,146 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 1 ms
4,380 KB |
| testcase_04 | AC | 147 ms
17,416 KB |
| testcase_05 | AC | 763 ms
17,908 KB |
| testcase_06 | AC | 1,118 ms
17,840 KB |
| testcase_07 | AC | 3,872 ms
17,908 KB |
| testcase_08 | AC | 3,543 ms
18,116 KB |
| testcase_09 | AC | 3,594 ms
17,908 KB |
| testcase_10 | AC | 1,695 ms
19,984 KB |
| testcase_11 | AC | 1,909 ms
20,024 KB |
| testcase_12 | AC | 1,865 ms
20,040 KB |
| testcase_13 | AC | 1,532 ms
19,924 KB |
| testcase_14 | AC | 1,284 ms
19,088 KB |
| testcase_15 | AC | 950 ms
19,108 KB |
| testcase_16 | AC | 3,298 ms
20,668 KB |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | AC | 2,621 ms
18,880 KB |
| testcase_20 | AC | 1,732 ms
15,336 KB |
| testcase_21 | AC | 1,249 ms
18,844 KB |
| testcase_22 | AC | 1,229 ms
18,708 KB |
| testcase_23 | AC | 2 ms
4,380 KB |
| testcase_24 | AC | 1 ms
4,376 KB |
| testcase_25 | AC | 1 ms
4,376 KB |
ソースコード
bool TEST = false;
using namespace std;
#include<bits/stdc++.h>
#include<fstream>
#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
#define rrep(i,n) for(ll (i)=(ll)(n)-1;(i)>=0;i--)
#define range(i,start,end,step) for(ll (i)=start;(i)<(ll)(end);(i)+=(step))
#define rrange(i,start,end,step) for(ll (i)=start;(i)>(ll)(end);(i)+=(step))
#define dump(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << (x) << "\n";
#define spa << " " <<
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T>>;
template<typename T, typename T2> using P = pair<T, T2>;
template<typename T, typename T2> using M = map<T, T2>;
template<typename T> using S = set<T>;
template<typename T, typename T2> using UM = unordered_map<T, T2>;
template<typename T> using PQ = priority_queue<T, V<T>, greater<T>>;
template<typename T> using rPQ = priority_queue<T, V<T>, less<T>>;
template<class T>vector<T> make_vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vec(size_t a, Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}
template<class SS, class T> ostream& operator << (ostream& os, const pair<SS, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;}
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template <class T> void UNIQUE(vector<T> &x) {sort(all(x));x.erase(unique(all(x)), x.end());}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
void fail() { cout << -1 << '\n'; exit(0); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
template<typename T> void debug(vector<vector<T>>&v){for(ll i=0;i<v.size();i++)
{cerr<<v[i][0];for(ll j=1;j<v[i].size();j++)cerr spa v[i][j];cerr<<"\n";}};
template<typename T> void debug(vector<T>&v){if(v.size()!=0)cerr<<v[0];
for(ll i=1;i<v.size();i++)cerr spa v[i];
cerr<<"\n";};
template<typename T> void debug(priority_queue<T>&v){V<T> vals; while(!v.empty()) {cerr << v.top() << " "; vals.push_back(v.top()); v.pop();} cerr<<"\n"; for(auto val: vals) v.push(val);}
template<typename T, typename T2> void debug(map<T,T2>&v){for(auto [k,v]: v) cerr << k spa v << "\n"; cerr<<"\n";}
template<typename T, typename T2> void debug(unordered_map<T,T2>&v){for(auto [k,v]: v) cerr << k spa v << "\n";cerr<<"\n";}
V<int> listrange(int n) {V<int> res(n); rep(i,n) res[i]=i; return res;}
template<typename T> P<T,T> divmod(T a, T b) {return make_pair(a/b, a%b);}
const ll INF = (1ll<<62);
// const ld EPS = 1e-10;
// const ld PI = acos(-1.0);
using VALUE = char;
VALUE unit = 1;
VALUE merge(VALUE val, VALUE other) {
VALUE tmp;
if (val==0 || other==0) tmp = 0;
else if (val==2 && other==2) tmp = 0;
else tmp = max(val, other);
return tmp;
}
VALUE add_node(VALUE val, int c, int D, int x) {
VALUE tmp = val;
if (c<D-x && c>x) {
tmp = 0;
} else if (c<D-x) {
if (val==1) tmp = 1;
else tmp = 0;
} else if (c>x) {
if (val==1) tmp = 2;
}
return tmp;
}
void Main(){
// tree input (unweighted)
int n,u,v;
int c;
cin >> n;
// unit = V<int>();
int D = 0;
VV<P<int,int>> ns(n, V<P<int,int>>());
rep(i,n-1) {
cin >> u >> v >> c;
u--;
v--;
ns[u].emplace_back(c,v);
ns[v].emplace_back(c,u);
chmax(D, c);
}
int root = 0;
rep(u,n) if (ns[u].size()>=2) {
root = u;
break;
}
auto sub = [&] (int x) {
V<VALUE> d0(n); // d0[u]: subtree u
V<int> par(n, -1);
V<int> pv(n, -1);
par[root] = root;
V<int> order;
stack<int> s;
s.push(root);
while (!s.empty()) {
auto u = s.top();
s.pop();
if (u<0) {
u = ~u;
auto val = unit;
for (auto [c,v] : ns[u]) {
if (par[v]!=u) continue;
val = merge(val, add_node(d0[v], c, D, x));
}
d0[u] = val;
} else {
order.push_back(u);
s.push(~u);
for (auto [c,v]: ns[u]) {
if (par[v]>=0) continue;
if (c<D-x && c>x) return 0;
s.push(v);
par[v] = u;
pv[v] = c;
}
}
}
V<VALUE> d1(n); // d1[u]: subtree par[u]
d1[root] = unit;
int res = 0;
for (auto u: order) {
V<VALUE> cl = {unit};
V<VALUE> cr = {unit};
VALUE vl = unit;
VALUE vr = unit;
rep(i, ns[u].size()) {
v = ns[u][i].second;
auto c = ns[u][i].first;
if (par[v]==u) {
vl = merge(vl, add_node(d0[v], c, D, x));
cl.push_back(vl);
}
v = ns[u][ns[u].size()-1-i].second;
c = ns[u][ns[u].size()-1-i].first;
if (par[v]==u) {
vr = merge(vr, add_node(d0[v], c, D, x));
cr.push_back(vr);
}
}
reverse(all(cr));
int i = 0;
for (auto [c, v] : ns[u]) {
if (par[v]!=u) continue;
VALUE tmp = u==root? unit : add_node(d1[u], pv[u], D, x);
auto val = merge(merge(tmp, cl[i]), cr[i+1]);
d1[v] = val;
// if (v==3) cout << "hoge" spa val spa tmp spa c << endl;
i++;
}
}
// cout << x spa root << endl;
// debug(d0);
// debug(d1);
int ok = 0;
rep(u,n) {
V<int> count(3);
if (true) {
auto c = pv[u];
count[add_node(d1[u], c, D, x)]++;
}
for (auto [c,v] : ns[u]) {
if (par[u]==v) {
count[add_node(d1[u], c, D, x)]++;
} else {
count[add_node(d0[v], c, D, x)]++;
}
}
if (count[0]==0 && count[2]<=2) ok = 1;
// cout << u << endl;
// debug(count);
}
return ok;
};
ll ng = -1;
ll ok = D;
while (abs(ng-ok)>1) {
ll mm = (ok+ng)/2;
if (sub(mm)) ok = mm;
else ng = mm;
}
cout << ok << endl;
}
int main(void){
std::ifstream in("tmp_in");
if (TEST) {
std::cin.rdbuf(in.rdbuf());
std::cout << std::fixed << std::setprecision(15);
} else {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(15);
}
Main();
}