fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const unsigned long long MOD = 1e9 + 7;
  5. const int INF = (int)2e9 + 7;
  6. const long long LINF = (long long)1e18;
  7. const unsigned long long mod1 = 183453789;
  8. const unsigned long long mod2 = 1234567891;
  9. const int P1 = 337, P2 = 263;
  10.  
  11. template<typename T>
  12. T input(){
  13.     T ans = 0, m = 1; char c = ' ';
  14.     while (!((c >= '0' && c <= '9') || c == '-')) c = getchar();
  15.     if (c == '-') m = -1, c = getchar();
  16.     while (c >= '0' && c <= '9') ans = ans * 10 + (c - '0'), c = getchar();
  17.     return ans * m;
  18. }
  19.  
  20. string nextString(bool flag = false){
  21.     char ch; string ans = "";
  22.     do { ch = getchar(); } while(ch <= ' ');
  23.     while(1) {
  24.         ans += ch; ch = getchar();
  25.         if ( (!flag && ch <= ' ') || (flag && ch < ' ') ) break;
  26.     }
  27.     return ans;
  28. }
  29. char nextChar(){
  30.     char ch;
  31.     do {ch = getchar(); } while(ch <= ' ');
  32.     return ch;
  33. }
  34. void read(string& s){ s = nextString(); }
  35. void read(char& c){ c = nextChar(); }
  36. template<typename T> void read(T& a){ a = input<T>(); }
  37. template<typename T, typename... R> void read(T& a, R&... r){ read(a); read(r...); }
  38.  
  39. const int N = 1e5 + 10;
  40.  
  41. struct Segment {
  42.     int l, r;
  43.     Segment() : l(-INF), r(INF) {}
  44.     Segment(int l, int r) : l(l), r(r) {}
  45.     Segment operator+(const Segment& other) const {
  46.         return Segment(l + other.l, r + other.r);
  47.     }
  48.     bool operator==(const Segment& other) const {
  49.         return l == other.l && r == other.r;
  50.     }
  51.     bool isOk() {
  52.         return l <= r;
  53.     }
  54. };
  55.  
  56. Segment combine(const Segment& a, const Segment& b){
  57.     return Segment(max(a.l, b.l), min(a.r, b.r));
  58. }
  59.  
  60. vector < Segment > pref[N];
  61. vector < Segment > suff[N];
  62.  
  63. vector < int > g[N];
  64. Segment seg[N], f[N], fd[N];
  65. int ans[N];
  66.  
  67. void preDfs(int v, int p){
  68.     for (auto to: g[v]){
  69.         if (to == p) continue;
  70.         preDfs(to, v);
  71.         pref[v].push_back(f[to]);
  72.         suff[v].push_back(f[to]);
  73.         fd[v] = combine(fd[v], f[to]);
  74.     }
  75.     int k = (int)pref[v].size();
  76.     for (int i = 1; i < k; ++ i){
  77.         pref[v][i] = combine(pref[v][i], pref[v][i - 1]);
  78.         suff[v][k - i - 1] = combine(suff[v][k - i - 1], suff[v][k - i]);
  79.     }
  80.     f[v] = fd[v] + seg[v];
  81.     if (fd[v] == Segment())
  82.         f[v] = seg[v];
  83.     if (!fd[v].isOk())
  84.         f[v] = {INF, -INF};
  85. }
  86.  
  87. void dfs(int v, int p, const Segment& cur){
  88.     //cerr << v + 1 << " (" << cur.l << ", " << cur.r << ") (" << fd[v].l << ", " << fd[v].r << ")" << endl;
  89.     ans[v] = combine(cur, fd[v]).isOk();
  90.     for (int i = 0, ptr = 0; i < g[v].size(); ++ i){
  91.         int to = g[v][i];
  92.         if (to == p) continue;
  93.         Segment newSeg = cur;
  94.         if (ptr) 
  95.             newSeg = combine(newSeg, pref[v][ptr - 1]);
  96.         if (ptr < (int)pref[v].size() - 1) 
  97.             newSeg = combine(newSeg, suff[v][ptr + 1]);
  98.         if (newSeg == Segment())
  99.             newSeg = seg[v];
  100.         else
  101.         if (!newSeg.isOk())
  102.             newSeg = {INF, -INF};
  103.         else
  104.             newSeg = newSeg + seg[v];
  105.  
  106.         dfs(to, v, newSeg);
  107.         ptr ++;
  108.     }
  109. }
  110.  
  111. int32_t main(){
  112.     ios_base::sync_with_stdio(0); cin.tie(0);
  113.     #ifdef LOCAL
  114.         freopen("in.txt", "r", stdin);
  115.         freopen("out.txt", "w", stdout);
  116.     #else
  117.         freopen("lamps.in", "r", stdin);
  118.         freopen("lamps.out", "w", stdout);
  119.     #endif
  120.     int n; read(n);
  121.     for (int i = 0; i < n - 1; ++ i){
  122.         int u, v;
  123.         read(u, v);
  124.         u --, v --;
  125.         g[u].push_back(v);
  126.         g[v].push_back(u);
  127.     }
  128.     for (int i = 0; i < n; ++ i){
  129.         read(seg[i].l, seg[i].r);
  130.     }
  131.     preDfs(0, -1);
  132.     dfs(0, -1, Segment());
  133.     for (int i = 0; i < n; ++ i){
  134.         cout << ans[i] << " ";
  135.     }
  136. }
Time limit exceeded #stdin #stdout 5s 9712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sw5Deg
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!