oj.uz

Submission #601399

# Submission time Handle Problem Language Result Execution time Memory
601399 2022-07-21T20:00:31 Z MohammadAghil Pastiri (COI20_pastiri) C++17
23 / 100
 1000 ms 158112 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

vector<int> adj[maxn], nd;
set<int> st[maxn];
int par[maxn][lg], h[maxn], cnt[maxn], nxt[maxn], vl[maxn], mn[maxn];
bool ban[maxn];

void dfs(int r, int p){
     par[r][0] = p;
     // er(r);
     rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
     // er(r);
     for(int c: adj[r]) if(c - p) h[c] = h[r] + 1, dfs(c, r);
}

int lca(int u, int v){
     if(h[u] > h[v]) swap(u, v);
     per(i,lg-1,0) if(h[par[v][i]] >= h[u]) v = par[v][i];
     if(u == v) return u;
     per(i,lg-1,0) if(par[v][i] - par[u][i]) u = par[u][i], v = par[v][i];
     return par[u][0]; 
}

void dfs2(int r, int p){
     cnt[r] = 1;
     for(int c: adj[r]) if(c - p && !ban[c]) dfs2(c, r), cnt[r] += cnt[c];
}

int find_cent(int r, int p, int tot){
     for(int c: adj[r]) if(c - p && !ban[c] && (cnt[c]<<1) > tot) return find_cent(c, r, tot);
     return r;
}

void decom(int r, int tp){
     dfs2(r, -1);
     r = find_cent(r, -1, cnt[r]);
     nxt[r] = tp, ban[r] = true;
     for(int c: adj[r]) if(!ban[c]) decom(c, r);
}

int dist(int u, int v){
     return h[u] + h[v] - (h[lca(u, v)]<<1);
}

void bfs(){
     fill(mn, mn + maxn, inf);
     deque<int> q;
     for(int c: nd) mn[c] = 0, q.pb(c);
     while(sz(q)){
          int r = q.front(); q.pop_front();
          for(int c: adj[r]) if(mn[c] == inf) mn[c] = mn[r] + 1, q.pb(c);
     }
}


int main(){ IOS();
     int n, k; cin >> n >> k;
     rep(i,1,n){
          int u, v; cin >> u >> v; u--, v--;
          adj[u].pb(v), adj[v].pb(u);
     }
     nd.resize(k);
     rep(i,0,k) cin >> nd[i], nd[i]--;

     dfs(0, 0);
     // er(n);
     decom(0, -1), bfs();

     // rep(i,0,n) er(i+1, mn[i]);

     sort(all(nd), [&](int i, int j){ return h[i] > h[j]; });
     vector<int> ans;
     auto add = [&](int u){
          ans.pb(u);
          int cr = u;
          while(cr + 1){
               int d = dist(u, cr);
               // er(cr);
               if(mn[u] >= d) st[cr].insert(mn[u] - d);
               cr = nxt[cr];
          }
     };

     auto chk = [&](int u){
          int cr = u;
          while(cr + 1){
               // er(sz(st[cr]));
               if(st[cr].find(dist(cr, u)) != end(st[cr])) return true;
               // er(sz(st[cr]));
               cr = nxt[cr];
          }
          return false;
     };

     auto get = [&](int u){
          int k = u;
          per(i,lg-1,0) if(h[u] - h[par[k][i]] == mn[par[k][i]]) k = par[k][i];
          return k;
     };

     for(int c: nd){
          if(chk(c)) continue;
          // er(c+1, get(c)+1);
          add(get(c));
     }

     cout << sz(ans) << '\n'; sort(all(ans));
     for(int c: ans) cout << ++c << ' '; cout << '\n';
     return 0; 
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:132:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  132 |      for(int c: ans) cout << ++c << ' '; cout << '\n';
      |      ^~~
pastiri.cpp:132:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  132 |      for(int c: ans) cout << ++c << ' '; cout << '\n';
      |                                          ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 148432 KB Output is correct
2 Correct 391 ms 148520 KB Output is correct
3 Correct 388 ms 148456 KB Output is correct
4 Execution timed out 1091 ms 158112 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 38228 KB Output is correct
2 Correct 20 ms 38260 KB Output is correct
3 Correct 762 ms 109824 KB Output is correct
4 Correct 702 ms 112076 KB Output is correct
5 Execution timed out 1084 ms 107296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 18 ms 37844 KB Output is correct
3 Correct 19 ms 37836 KB Output is correct
4 Correct 19 ms 37796 KB Output is correct
5 Correct 19 ms 37844 KB Output is correct
6 Correct 19 ms 37876 KB Output is correct
7 Correct 18 ms 37744 KB Output is correct
8 Correct 17 ms 37740 KB Output is correct
9 Correct 18 ms 37844 KB Output is correct
10 Correct 17 ms 37716 KB Output is correct
11 Correct 18 ms 37748 KB Output is correct
12 Correct 16 ms 37588 KB Output is correct
13 Correct 17 ms 37756 KB Output is correct
14 Correct 19 ms 37792 KB Output is correct
15 Correct 19 ms 37884 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 108312 KB Time limit exceeded
2 Halted 0 ms 0 KB -