Submission #1127356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127356		modwwe	Capital City (JOI20_capital_city)	C++20	100 / 100	1589 ms	299784 KiB

capital_city

#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
void phongbeo();
const int inf = 1e14;
const ll mod2 = 1e9+7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,ans ;
int kk;
int el = 19;
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    //modwwe
    phongbeo(),down
    // checktime
}
int color[200001],st[18][200001],in[200001],depth[200001],ou[200001],low[4000001],num[4000001];
vector<int> v[4000001],ke[200001],lc[200001];
int id[18][200001];
bool cek[4000001],vis[200001];
void noi(int x,int y)
{
    int par=color[x];
    for(int i=0; i<18; i++)
        if(bit(y,i))
        {
            v[par].pb(id[i][x]);
            x=st[i][x];
        }
}
bool check(int x,int y)
{
    if(in[x]<=in[y]&&in[y]<=ou[x]) return 1;
    return 0;
}
int lca(int x,int y)
{
    if(check(x,y)) return x;
    for(int i=17; i>=0; --i)
        if(!check(st[i][x],y))
            x=st[i][x];
    return st[0][x];
}
void dfs(int x,int y)
{
    in[x]=++dem;
    st[0][x]=y;
    depth[x]=depth[y]+1;
    for(auto f:ke[x])
        if(f^y)
            dfs(f,x);
    ou[x]=dem;
}
stack<int> s;
void dfs2(int x)
{
    num[x]=low[x]=++dem;
    s.push(x);
    for(auto f:v[x])
    {
        if(num[f]==0) dfs2(f);
        if(low[f]==inf)cek[x]=1;
        low[x]=min(low[x],low[f]);
    }
    if(low[x]==num[x])
    {
        s2=-1;
        s3=0;
        bool de=0;
        while(s2!=x)
        {
            s2=s.top();
            s.pop();
            low[s2]=inf;
            if(s2<=k&&!vis[s2])
                s3++,vis[s2]=1;
            if(cek[s2])de=1;
        }
        if(!de)s4=min(s4,s3);
    }
}
void phongbeo()
{
    cin>>n>>k;
    for(int i=1; i<n; i++)
        cin>>l>>r,ke[l].pb(r),ke[r].pb(l);
    for(int i=1; i<=n; i++)
        cin>>color[i],id[0][i]=color[i],lc[color[i]].pb(i);
    dfs(1,0);
    ou[0]=n;
    dem=k;
    for(int i=1; i<18; i++)
        for(int j=1; j<=n; j++)
        {
            id[i][j]=++dem;
            v[id[i][j]].pb({id[i-1][j]});
            v[id[i][j]].pb({id[i-1][st[i-1][j]]});
            st[i][j]=st[i-1][st[i-1][j]];
        }
    for(int i=1; i<=k; i++)
    {
        int s=0;
        for(auto x:lc[i])
        {
            if(s==0) s=x;
            else s=lca(s,x);
        }
        for(auto x:lc[i])
            noi(x,depth[x]-depth[s]+1);
    }
    s4=n+1;
    dem=0;
    for(int i=1; i<=k; i++)
        if(!num[i])
            dfs2(i);
    cout<<s4-1;
}

Compilation message (stderr)

capital_city.cpp:37:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+14' to '2147483647' [-Woverflow]
   37 | const int inf = 1e14;
      |                 ^~~~
capital_city.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main()
      | ^~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
capital_city.cpp:78:9: note: in expansion of macro 'fin'
   78 |         fin(task2);
      |         ^~~
capital_city.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
capital_city.cpp:79:9: note: in expansion of macro 'fou'
   79 |         fou(task2);
      |         ^~~
capital_city.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
capital_city.cpp:83:9: note: in expansion of macro 'fin'
   83 |         fin(task);
      |         ^~~
capital_city.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
capital_city.cpp:84:9: note: in expansion of macro 'fou'
   84 |         fou(task);
      |         ^~~

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