Submission #1117381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117381		ntdaccode	Synchronization (JOI13_synchronization)	C++17	100 / 100	508 ms	34120 KiB

synchronization

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=2e5+10;
const int N=1e3+10;
const int mod=1e9+7;

int n, q, m, c[M];
vector<ii> ke[M];

int sz[M], par[M], d[M];
int con[M], cha[M], g[M];
int f[M];

void dfs(int u,int p)
{
   sz[u] = 1;
   for(ii node : ke[u]) {
      int v = node.first, idx = node.second;
      if(v == p) continue;
      cha[idx] = u;
      con[idx] = v;
      par[v] = u;
      d[v] = d[u] + 1;
      dfs(v,u);
      sz[u] += sz[v];
   }
}

int pos[M], arr[M], cnt = 0;
int head[M], id[M], chain = 0;

void hld(int u,int p)
{
   //cerr << chain << " " << head[chain] << " " << u << "\n";
   if(!head[chain]) head[chain] = u;
   id[u] = chain;
   pos[u] = ++ cnt;
   arr[cnt] = u;

   int nxt = 0;
   for(ii node : ke[u]) {
         int v = node.first;
      if(v == p) continue;
      if(sz[v] > sz[nxt]) nxt = v;
   }
   if(nxt) hld(nxt,u);
   for(ii node : ke[u]) {
      int v = node.first;
      if(v == p || v == nxt) continue;
      chain ++ ;
      hld(v,u);
   }

}

ii t[4 * M];
void build(int s, int l, int r)
{
   if(l == r) {
      t[s] = {d[arr[l]],arr[l]};
      return ;
   }
   int mid = (l + r)/2;
   build(s * 2, l, mid);
   build(s * 2 + 1, mid + 1, r);
   t[s] = max(t[s * 2],t[s * 2 + 1]);
}

void upd(int s, int l, int r, int p, int val)
{
   if(l > p || r < p) return ;
   if(l == r) {
      t[s].first = val;
      return ;
   }
   int mid = (l + r)/2;
   upd(s * 2, l, mid, p, val);
   upd(s * 2 + 1, mid + 1, r, p, val);
   t[s] = max(t[s * 2],t[s * 2 + 1]);
}

ii get(int s,int l,int r,int u,int v)
{
   if(l > v || r < u) return {-1,-1};
   if(u <= l && r <= v) return t[s];
   int mid = (l + r)/2;
   return max(get(s * 2, l, mid, u, v),get(s * 2 + 1, mid + 1, r, u, v));
}



int query(int u,int v)
{
   //if(u == 1 && v == 5)
   ii res = {0,0};
   while(id[u] != id[v]) {
      if(id[u] > id[v]) {
         res = max(res,get(1,1,n,pos[head[id[u]]],pos[u]));
         u = par[head[id[u]]];
      }
      else {
         res = max(res,get(1,1,n,pos[head[id[v]]],pos[v]));
         v = par[head[id[v]]];
      }
   }
   if(pos[v] < pos[u]) res = max(res,get(1,1,n,pos[v],pos[u]));
   else res = max(res,get(1,1,n,pos[u],pos[v]));
   return res.second;
}

bool dd[M];
int ans[M];


int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n >> m >> q;
  for(int i = 1;i <= n - 1; i++) {
      int u,v;
      cin >> u >> v;
      ke[u].pb({v,i});
      ke[v].pb({u,i});
  }
  dfs(1,0);
  hld(1,0);
  build(1,1,n);
  for(int i = 1;i <= n; i++) f[i] = 1;
  for(int i = 1;i <= m; i++) {
      int idx;
      cin >> idx;
      if(!dd[idx]) {
         int u = cha[idx], v = con[idx];
         int root_u = query(1,u), root_v = query(1,v);
         f[root_u] = f[root_u] + f[root_v] - g[idx];
         //cout << f[root_u] << " ";
         //cout << u << " " << v << " " << root_u << " " << root_v << "\n";
         upd(1,1,n,pos[v],-1);
         dd[idx] = true;
      }
      else {
         int u = cha[idx], v = con[idx];
         upd(1,1,n,pos[v],d[v]);
         int root_u = query(1,u), root_v = query(1,v);
         f[root_v] = f[root_u];
         g[idx] = f[root_u];
         //cout << f[root_v]  << " ";
         //cout << u << " " << v << " " << root_u << " " << root_v << "sa\n";
         dd[idx] = false;
      }
  }
  for(int i = 1;i <= n; i++) {
      int u = query(1,i);
      ans[i] = f[u];
  }
  while(q--) {
      int u;
      cin >> u;
      cout << ans[u] << "\n";
  }

}

Compilation message (stderr)

synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:129:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
synchronization.cpp:134:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:135:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40