Submission #1105901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105901		ntdaccode	Two Currencies (JOI23_currencies)	C++17	100 / 100	1000 ms	63816 KiB

currencies

#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=1e5+10;
const int N=1e3+10;
const int mod=1e9+7;
int n,m,q;
int uu[M],vv[M];
vector<int> ke[M];
// dfs
int num[M],tail[M],up[M][20],cnt=0;
void dfs(int u,int p)
{
  num[u]=++cnt;
  fori(i,1,17) up[u][i]=up[up[u][i-1]][i-1];
  for(int v:ke[u]) {
    if(v==p) continue;
    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=17;i>=0;i--) if(!anc(up[u][i],v)) u=up[u][i];
  return up[u][0];
}
// bit
int bit[M];
void upd(int idx,int val)
{
  if(idx==0) return ;
  while(idx<=n) {
    bit[idx]+=val;
    idx+=idx&(-idx);
  }
}
int get(int idx)
{
  int res=0;
  while(idx>0) {
    res+=bit[idx];
    idx-=idx&(-idx);
  }
  return res;
}
int query(int u,int v)
{
  int x=lca(u,v);
  return get(num[u])+get(num[v])-2*get(num[x]);
}
// solve
int ed[M],st[M],xx[M],yy[M];
int l[M],r[M],ret[M];
vector<int> Q[M];
ii edge[M];
void solve()
{
  fori(i,1,q) l[i]=1,r[i]=m;
  bool process=1;
  while(process) {
      process=0;
      fori(i,1,q) {
        if(l[i]>r[i]) continue;
        Q[(l[i]+r[i])/2].pb(i);
        process=1;
      }
      if(!process) break;
      fori(i,1,m) {

        int v=edge[i].second;
        int w=edge[i].first;
        upd(num[v],w);
        upd(tail[v]+1,-w);
        for(int idx : Q[i]) {
           // cout << i << " " << st[idx] << " " << ed[idx] << " " << query(st[idx],ed[idx]) << "\n";
          if(query(st[idx],ed[idx])<=yy[idx]) {
            ret[idx]=i;
            l[idx]=i+1;
          }
          else r[idx]=i-1;
        }
      }
      fori(i,1,m) Q[i].clear();
      fori(i,1,n) bit[i]=0;
  }

}

void solve2()
{
  fori(i,1,q) l[i]=r[i]=0;
  fori(i,1,q) Q[ret[i]].pb(i);
  fori(i,1,m) {
    int v=edge[i].second;
    upd(num[v],1);
    upd(tail[v]+1,-1);
    //cout << v << " ";
    for(int idx : Q[i]) {
      l[idx]=query(st[idx],ed[idx]);
    }
  }
  fori(i,1,q) {
    r[i]=query(st[i],ed[i]);
    //cout << l[i] << " " << r[i] << "\n";
    if(r[i]-l[i]<=xx[i]) cout << xx[i]-(r[i]-l[i]) << "\n";
    else cout << -1 << "\n";
  }
}

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;
  fori(i,1,n-1) {
    cin >> uu[i] >> vv[i] ;
    ke[uu[i]].pb(vv[i]);
    ke[vv[i]].pb(uu[i]);
  }
  up[1][0]=1;
  dfs(1,0);
  fori(i,1,m) {
    int p,c;
    cin >> p >> c;
    if(up[uu[p]][0]==vv[p]) edge[i]={c,uu[p]};
    else  edge[i]={c,vv[p]};
  }
  sort(edge+1,edge+m+1);
  fori(i,1,q) {
    cin >> st[i] >> ed[i] >> xx[i] >> yy[i];
  }
  solve();
  solve2();

}

Compilation message (stderr)

currencies.cpp: In function 'int32_t main()':
currencies.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.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:130:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
currencies.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".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32