Submission #566914

#	Time	Username	Problem	Language	Result	Execution time	Memory
566914		azberjibiou	Star Trek (CEOI20_startrek)	C++17	0 / 100	5 ms	7508 KiB

startrek

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mxN=100025;
const int mxM=300005;
const int mxK=1000000000;
const ll MOD=1000'000'007;
const ll INF=1000000000000000005;
ll N, D;
vector <int> v[mxN];
int outw[mxN];
int downw[mxN], upw[mxN];
bool W[mxN];
int degL[mxN];
vector <int> v1[mxN], v2[mxN];
int sizw1[mxN], leafw2[mxN], sizl2[mxN], par1[mxN], par2[mxN];
ll numw;
int match[mxN];
void dfs_downw(int now, int pre)
{
    for(int nxt : v[now])   if(nxt!=pre)
    {
        dfs_downw(nxt, now);
    }
    downw[now]=(outw[now]==0 ? 1 : 0);
    if(now!=1)  outw[pre]+=downw[now];
}
void dfs_upw(int now, int pre)
{
    if(now!=1)
    {
        upw[now]=(outw[pre]-downw[now]==0 ? 1 : 0);
        outw[now]+=upw[now];
    }
    for(int nxt : v[now])   if(nxt!=pre)
    {
        dfs_upw(nxt, now);
    }
}
int findpar(int a, int typ)
{
    if(typ==1)  return (par1[a]==a ? a : par1[a]=findpar(par1[a], 1));
    else    return (par2[a]==a ? a : par2[a]=findpar(par2[a], 2));
}
void onion(int a, int b, int typ)
{
    int p=findpar(a, typ), q=findpar(b, typ);
    if(typ==1)
    {
        par1[p]=q;  sizw1[q]+=sizw1[p];
    }
    else
    {
        par2[p]=q;  sizl2[q]+=sizl2[p]; leafw2[q]+=leafw2[p];
    }
}
int dfs_match(int now, int pre)
{
    for(int nxt : v[now])   if(nxt!=pre && W[nxt] && degL[nxt]==0)
    {
        int tmp=dfs_match(nxt, now);
        if(tmp!=0)  match[now]=tmp, match[tmp]=now;
    }
    if(match[now])  return 0;
    else    return now;
}
int dfs_1(int now, int pre)
{
    int sum=1;
    for(int nxt : v[now])   if(nxt!=pre && W[nxt] && degL[nxt]==0)
    {
        sum+=dfs_1(nxt, now);
    }
    return sum;
}
int main()
{
    gibon
    cin >> N >> D;
    for(int i=1;i<N;i++)
    {
        int a, b;   cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs_downw(1, -1);
    dfs_upw(1, -1);
    for(int i=1;i<=N;i++)
    {
        W[i]=(outw[i]>=1);
        numw+=W[i];
    }
    for(int i=1;i<=N;i++)
    {
        for(int ele : v[i])
        {
            if(!W[ele]) degL[i]++;
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(!W[i] || degL[i])    continue;
        for(int ele : v[i]) if(W[ele] && degL[ele]==0)  v1[i].push_back(ele);
    }
    for(int i=1;i<=N;i++)
    {
        if(!W[i])
        {
            for(int ele : v[i]) if(degL[ele]<3) v2[i].push_back(ele);
        }
        else if(degL[i]<3)
        {
            for(int ele : v[i]) if(!W[ele]) v2[i].push_back(ele);
        }
    }
    for(int i=1;i<=N;i++)
    {
        par1[i]=par2[i]=i;
        if(degL[i]==0 && W[i])  sizw1[i]=1;
        if(v2[i].size()==1 && W[i]) leafw2[i]=1;
        if(!W[i])   sizl2[i]=1;
    }
    for(int i=1;i<=N;i++)
    {
        for(int ele : v1[i])    if(ele<i)
        {
            onion(ele, i, 1);
        }
        for(int ele : v2[i])    if(ele<i)
        {
            onion(ele, i, 2);
        }
    }
    dfs_match(1, -1);
    if(W[1])
    {
        ll ans=N*N;
        if(degL[1]==0)  ans-=(N-numw)*(dfs_1(match[1], 1)+1)/2;
        if(v2[1].size()==1) ans-=(N-numw)*sizl2[findpar(1, 2)];
        cout << ans%MOD;
    }
    else
    {
        ll ans=0;
        ans+=(N-numw)*sizl2[findpar(1, 2)];
        cout << ans%MOD;
    }
}
/*
10 1
3 9
9 6
4 5
7 9
8 2
0 5
3 4
2 9
8 1

*/

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15