oj.uz

Submission #601403

# Submission time Handle Problem Language Result Execution time Memory
601403 2022-07-21T20:08:01 Z MohammadAghil Pastiri (COI20_pastiri) C++17
23 / 100
 1000 ms 151292 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;
     rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
     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 dfs3(int r){
     if(r == -1) return 0;
     if(vl[r] == inf) return vl[r] = dfs3(nxt[r]) + 1;
     return vl[r];
}


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), decom(0, -1), bfs();
     fill(vl, vl + maxn, inf);
     rep(i,0,n) assert(dfs3(i) <= lg);

     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);
               if(mn[u] >= d) st[cr].insert(mn[u] - d);
               cr = nxt[cr];
          }
     };

     auto chk = [&](int u){
          int cr = u;
          while(cr + 1){
               if(st[cr].find(dist(cr, u)) != end(st[cr])) return true;
               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;
          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:130:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  130 |      for(int c: ans) cout << ++c << ' '; cout << '\n';
      |      ^~~
pastiri.cpp:130:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  130 |      for(int c: ans) cout << ++c << ' '; cout << '\n';
      |                                          ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 144108 KB Output is correct
2 Correct 433 ms 144352 KB Output is correct
3 Correct 447 ms 144432 KB Output is correct
4 Execution timed out 1048 ms 151292 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40160 KB Output is correct
2 Correct 23 ms 40132 KB Output is correct
3 Correct 838 ms 105292 KB Output is correct
4 Correct 767 ms 107952 KB Output is correct
5 Execution timed out 1071 ms 101280 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39764 KB Output is correct
2 Correct 21 ms 39792 KB Output is correct
3 Correct 21 ms 39792 KB Output is correct
4 Correct 20 ms 39668 KB Output is correct
5 Correct 22 ms 39792 KB Output is correct
6 Correct 22 ms 39780 KB Output is correct
7 Correct 22 ms 39732 KB Output is correct
8 Correct 22 ms 39784 KB Output is correct
9 Correct 22 ms 39680 KB Output is correct
10 Correct 20 ms 39724 KB Output is correct
11 Correct 20 ms 39588 KB Output is correct
12 Correct 20 ms 39552 KB Output is correct
13 Correct 21 ms 39788 KB Output is correct
14 Correct 21 ms 39788 KB Output is correct
15 Correct 24 ms 39764 KB Output is correct

Subtask #4
0 / 51.0

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