Submission #1277420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277420		sasde	Capital City (JOI20_capital_city)	C++20	100 / 100	472 ms	138904 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time   cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=1e6+5,lg=30,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,1,-1,1,-1};
int node,k,C[N],ans=1e9,query,edge,up[N][lg+5],h[N],tin[N],tout[N],timer,ma[N];
vector<int>ver[N],mau[N];
struct HLD {
  int n, curpos, curc;
  vector<int> st, lazy, sl, h, up, curhead, curid, pos, posend, arr;
  vector<vector<int>> edge;

  HLD() : curpos(0), curc(0) {};
  HLD(int _n) : n(_n), st(n * 4 + 5, 0), lazy(n * 4 + 5, 0), sl(n + 5), h(n + 5), up(n + 5),
  curhead(n + 5), curid(n + 5), pos(n + 5), posend(n+5), arr(n + 5), edge(n + 5) {
    curpos = curc = 0;
  };

  void addedge(int u, int v) {
    edge[u].emplace_back(v);
    edge[v].emplace_back(u);
  }
  void buildi(int id, int l, int r){
    if (r==l) {
      ver[id+k].emb(C[arr[l]]);
    // cerr<<id+k<<" "<<C[arr[l]]<<'\n';

      return;
    }
    int mid = (l + r) >> 1;
    buildi(id << 1, l, mid);
    buildi(id << 1 | 1, mid + 1,r);
    ver[id+k].emb((id<<1|1)+k);
    ver[id+k].emb((id<<1)+k);
    // cerr<<id+k<<" "<<(id<<1|1)+k<<" "<<(id<<1)+k<<'\n';
    // cerr<<(id<<1+k)
  }
  void update(int id, int l, int r, int u,int v, int val) {
    if(r<u||l>v)return;
    if (u<=l&&r<=v) {
      ver[val].emb(id+k);
    // cerr<<val<<" "<<id+k<<'\n';
      return;
    }
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, u,v, val);
    update(id << 1 | 1, mid + 1, r, u,v, val);
  }
  void dfs(int u, int cha) {
    sl[u] = 1;
    for (int v : edge[u]) {
      if (v == cha) continue;
      h[v] = h[u] + 1;
      up[v] = u;
      dfs(v, u);
      sl[u] += sl[v];
    }
  }

  void hld(int u, int cha) {
    if (!curhead[curc]) curhead[curc] = u;
    curid[u] = curc;
    pos[u] = ++curpos;
    arr[curpos] = u;
    int nxt = 0;
    for (int v : edge[u]) {
      if (v != cha && sl[v] > sl[nxt]) nxt = v;
    }
    if (nxt) hld(nxt, u);
    for (int v : edge[u]) {
      if (v != cha && v != nxt) {
        ++curc;
        hld(v, u);
      }
    }
    posend[u]=curpos;
  }
  
  void build(int goc){
    dfs(goc,-1);
    hld(goc,-1);
    buildi(1,1,n);
  }

  int lca(int u, int v) {
    int id=C[v];
    for(;curid[u]!=curid[v];v=up[curhead[curid[v]]]){
      if(h[curhead[curid[u]]]>h[curhead[curid[v]]])swap(u,v);
      update(1,1,n,pos[curhead[curid[v]]],pos[v],id);
    }
    if(h[u]>h[v])swap(u,v);
    update(1,1,n,pos[u],pos[v],id);
    return h[u] < h[v] ? u : v;
  }
};
int low[N],tt[N],num[N],vis[N];
stack<int>st;
void tarjan(int u){
    low[u]=num[u]=timer++;
    vis[u]=1;tt[u]=1;
    st.em(u);
    // cerr<<u<<" ";
    for(auto v:ver[u]){
        if(!vis[v])
            tarjan(v);
            if(vis[v]==1)
            low[u]=min(low[u],low[v]);
            tt[u]&=tt[v];
    }
    if(low[u]==num[u]){
        int v=-1,cnt=0;
        bool lf=tt[u];
        while(vis[u]==1){
          v=st.top();
          vis[v]=2;
          tt[v]=0;
          st.pop();
          // cerr <<v<<" ";
          cnt+=(v<=k);
        }
        // cerr<<'\n';
        if(lf)
        ans=min(ans,cnt-1);
    }

}
bool M2;
void solve(){
    cin >> node >> k;
    HLD hld(node);
    for(int i=1;i<node;++i){
        int u,v;
        cin >> u >> v;
        hld.addedge(u,v);
    }

    for(int i=1;i<=node;++i){
        cin >> C[i];
    }
    hld.build(1);
    for(int i=1;i<=node;++i){
        if(!ma[C[i]]){
            ma[C[i]]=i;
        }
        else ma[C[i]]=hld.lca(ma[C[i]],i);
    }
    for(int i=1;i<=k;++i)if(!vis[i])tarjan(i);

    cout << ans;
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #define task "aws"
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();cout<<'\n';
}
look_memory;
look_time;
}

Compilation message (stderr)

capital_city.cpp:176:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  176 | main()
      | ^~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:184:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:185:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59