Submission #1126188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126188		ntdaccode	Inside information (BOI21_servers)	C++20	0 / 96	27 ms	15172 KiB

servers

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


using namespace std;

typedef pair<long long,long long> ii;
typedef tuple<int,int,int> tp;

const int M = 5e5 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;

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

int num[M], tail[M], cnt = 0, up[M][20];
long long d[M];
void dfs(int u,int p = 0)
{
  num[u] = ++ cnt;
  for(int i = 1;i <= 19; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for(ii tmp : ke[u]) {
    int v = tmp.first;
    long long w = tmp.second;
    if(v == p) continue;
    d[v] = d[u] + w;
    up[v][0] = u;
    dfs(v,u);
  }
  tail[u] = cnt;
}

bool anc(int u,int v)
{
  return num[u] <= num[v] && tail[u] >= tail[v];
}

int lca(int u,int v)
{
  if(anc(u,v)) return u;
  if(anc(v,u)) return v;
  for(int i = 19; i >= 0; i--) if(!anc(up[u][i],v)) u = up[u][i];
  return up[u][0];
}


long long D[M];
bool cmp(const int &a,const int &b) {
  return num[a] < num[b];
}

bool dd[M];
void Init(int N, int A[], int B[], int DD[]) {
  n = N;
  for(int i = 0;i < n - 1; i++) {
      int u = A[i], v = B[i];
      long long w = DD[i];
      u ++, v ++;
      ke[u].pb({v,w});
      ke[v].pb({u,w});
  }
  up[1][0] = 1;
  dfs(1,0);
  for(int i = 1;i <= n; i++) ke[i].clear();
  for(int i = 1;i <= n; i++) D[i] = 1e15;
}
stack<int> sk;
vector<int> Q;
priority_queue<ii, vector<ii>, greater<ii> > h;
long long Query(int S, int X[], int T, int Y[]){
  bool ok = 0;
  for(int i = 0;i < S; i++) {
      X[i]++;
      int u = X[i];
      dd[u] = true;
    //  cout << u << " ";
      Q.pb(u);
  }
  for(int i = 0;i < T; i++) {
      Y[i]++;
      int u = Y[i];
      if(dd[u]) {
          ok = 1;
          break;
      }
      dd[u] = true;
      Q.pb(u);
  }
  if(ok == 1) {
    for(int v : Q) dd[v] = false;
    Q.clear();
    return 0;

  }

    sort(Q.begin(), Q.end(),cmp);
    Q.resize(unique(Q.begin(), Q.end()) - Q.begin());
    int m = Q.size();
    for(int i = 1;i <= m - 1; i++) {
        int x = lca(Q[i - 1],Q[i]);
        if(!dd[x]) Q.pb(x);
        dd[x] = true;
    }
    sort(Q.begin(), Q.end(), cmp);
    for(int v : Q) {
      while(!sk.empty() && !anc(sk.top(),v)) sk.pop();
      if(!sk.empty()) {
          long long w = d[v] - d[sk.top()];
          ke[v].pb({sk.top(),w});
          ke[sk.top()].pb({v,w});
      }
      sk.push(v);
    }
    while(!sk.empty()) {
        int v = sk.top();sk.pop();
        if(!sk.empty()) {
        int w = d[v] - d[sk.top()];
        ke[v].pb({sk.top(),w});
        ke[sk.top()].pb({v,w});
        }
    }
    for(int i = 0;i < S; i++) {
        int v = X[i];
        D[v] = 0;
        h.push({0,v});
    }
    while(!h.empty()) {
      int u;
      long long val;
      tie(val,u) = h.top();h.pop();
      if(D[u] < val) continue;
      for(ii tmp : ke[u]) {
        int v = tmp.first;
        long long w = tmp.second;
        if(D[v] > D[u] + w) {
          D[v] = D[u] + w;
          h.push({D[v],v});
        }
      }
    }
    long long kq = 1e15;
    for(int i = 0;i < T; i++) kq = min(kq, D[Y[i]]);
    for(int v : Q) {
      ke[v].clear();
      D[v] = 1e15;
      dd[v] = false;
    }
    Q.clear();
    return kq;

}


int uu[M], vv[M], ww[M];
int xx[M], yy[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 >> q;
  for(int i = 0;i < n - 1; i++) {
    cin >> uu[i] >> vv[i] >> ww[i];
  }
  Init(n,uu,vv,ww);
  while(q--) {
      int s,t;
      cin >> s >> t;
      for(int i = 0;i < s; i++) cin >> xx[i];
      for(int i = 0;i < t; i++) cin >> yy[i];
      cout << Query(s,xx,t,yy) << "\n";
  }


}

Compilation message (stderr)

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

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 2
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12
• Subtask 11: 0 / 17
• Subtask 12: 0 / 17