Submission #566941

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
566941	2022-05-23T06:40:24 Z	azberjibiou	Star Trek (CEOI20_startrek)	C++17	38 / 100	99 ms	21708 KB

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 sum=1;
    for(int nxt : v[match[now]])    if(nxt!=now && degL[nxt]==0)
    {
        sum+=dfs_1(nxt);
    }
    return sum;
}
void dfs(int now, int pre)
{
    for(int nxt : v[now])   if(pre!=nxt)
    {
        printf("(%d, %d)\n", now, nxt);
        dfs(nxt, now);
    }
}
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(1, -1);
    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(1);
        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;
    }
}
/*
15 1
11 10
2 1
13 3
14 2
1 3
9 10
6 7
9 4
1 6
3 12
8 11
0 14
5 13
12 9
*/

Subtask #1
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Incorrect	5 ms	7508 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	7380 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7416 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7416 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7508 KB	Output is correct
8	Correct	4 ms	7508 KB	Output is correct
9	Correct	4 ms	7508 KB	Output is correct
10	Correct	4 ms	7508 KB	Output is correct
11	Correct	4 ms	7508 KB	Output is correct

Subtask #5
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7416 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7508 KB	Output is correct
8	Correct	4 ms	7508 KB	Output is correct
9	Correct	4 ms	7508 KB	Output is correct
10	Correct	4 ms	7508 KB	Output is correct
11	Correct	4 ms	7508 KB	Output is correct
12	Correct	99 ms	20496 KB	Output is correct
13	Correct	89 ms	21708 KB	Output is correct
14	Correct	67 ms	18164 KB	Output is correct
15	Correct	75 ms	18668 KB	Output is correct
16	Correct	71 ms	17872 KB	Output is correct

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7416 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7508 KB	Output is correct
8	Correct	4 ms	7508 KB	Output is correct
9	Correct	4 ms	7508 KB	Output is correct
10	Correct	4 ms	7508 KB	Output is correct
11	Correct	4 ms	7508 KB	Output is correct
12	Correct	4 ms	7380 KB	Output is correct
13	Incorrect	5 ms	7508 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7416 KB	Output is correct
4	Correct	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7380 KB	Output is correct
7	Correct	4 ms	7508 KB	Output is correct
8	Correct	4 ms	7508 KB	Output is correct
9	Correct	4 ms	7508 KB	Output is correct
10	Correct	4 ms	7508 KB	Output is correct
11	Correct	4 ms	7508 KB	Output is correct
12	Correct	99 ms	20496 KB	Output is correct
13	Correct	89 ms	21708 KB	Output is correct
14	Correct	67 ms	18164 KB	Output is correct
15	Correct	75 ms	18668 KB	Output is correct
16	Correct	71 ms	17872 KB	Output is correct
17	Correct	4 ms	7380 KB	Output is correct
18	Incorrect	5 ms	7508 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Incorrect	5 ms	7508 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Submission #566941

Compilation message