Submission #810793

#	Time	Username	Problem	Language	Result	Execution time	Memory
810793		huynhyen1609	Logičari (COCI21_logicari)	C++14	110 / 110	192 ms	32852 KiB

Main

/*
                                 ..
                        .:^!7?JJJYJJJJ?77!!~^.
                   .:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:.
                 :!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~.
               :?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!.
             ^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^
           ~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^
         ^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7.
        !PY?777?77!7!7J?7!7?????JJ??7J??J^:.           .:!7?75GY:
      .JPJ!7!7?7?7!7!????????J?7??7J?YJ~.                .:!7?JGP^
     .JP?!7!!??7J7!!!?7J????7J7!!?!?7?7.                 .  ^??YG5:
     !P??7777?77??777?7?!7!777!?7J??J?^              :~~:  . ^?7YGY.
    :PY7??77!7~~:::.....:^^~!7??????J?^        .   .7PGGPY: . !?JPB~
   .Y5!!Y77!~:..            .:~7JJJ??J!.       . . .5GGGGP^ ..:J?JBJ
   ~G?!!?7!^.                  .^7JJYYJ7:.      . ..:~???~^^:..77?G5.
   !G!7?77:                     ..?J7~^~!77: .  .. ..^~~~~~~~:.!75B!
   !P77J7^                     ..~?:::^~!7?^ ........^~^^^^^:.^JYG?.
   !G???!:      .~77!:.        ..7?7?77~:....................^JPJ~
   :P5??7:     .JGGGGP!        ......  ..................:^!JP?^
    7BJ7J~     .JGGGGG~       . .....................::::^!7?JJ?!^.
    .YG?Y7^     .~7??~:::.     ..  .... ... ....::::::::::::^?~^!?J7:
     :PPJ??:    ..:^^^^^^:     .  .... ....::::^::::::::.:::^JP~..:75~
      :YGYJ?^.  .^^^^^^^:.        .....:::::::::::...:::..:.::JP!~~7Y~
        ~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~.
         :75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5?
           ?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^
           ~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY
            :!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP.
               :5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P:
               .P7::::::::::^::^^::::::::::::::::.:.........:::::J5.
           .   ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^
               :P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^
               .!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G?
                 ~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!.
                  .~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^  ..
                   .777?5J??YYYYY5?7777!!!!~!~~^^::.  .::
                        :!!~:.:^^:

        PENGUIN SO CUTE, I LOVE PENGUIN
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME ""
#define int long long
#define ii pair<int,int>
const int oo=1e9;
const int mod=1e9+7;
const int N=1e5;
const int LG=18;
const int Sqrt=350;
//int hx[]={0,0,1,-1,1,1,-1,-1},hy[]={1,-1,0,0,1,-1,1,-1};
int n,dp[N+5][2][2][2][2],p[N+5],A,B;
vector<int>graph[N+5];
int find(int v)
{
    if(p[v]==0)return v;
    return p[v]=find(p[v]);
}
bool union_(int a,int b)
{
    a=find(a);
    b=find(b);
    if(a==b)return false;
    p[b]=a;
    return true;
}
int cal(int u,int x,int y,int z,int t,int pre)
{
    int &res=dp[u][x][y][z][t];
    if(res!=-1)return res;
    if(u==A&&x!=z)return res=oo;
    if(u==B&&x!=t)return res=oo;
    if(u==B&&y&&z)return res=oo;
    bool kt=false;
    if(y)kt=true;
    if(u==A&&t)kt=true;
    if(u==B&&z)kt=true;
    int sum=x;
    for(int v:graph[u])
        if(v!=pre)sum+=cal(v,0,x,z,t,u);
    res=oo;
    if(kt)res=sum;
    else
    {
        for(int v:graph[u])
            if(v!=pre)res=min(res,sum-cal(v,0,x,z,t,u)+cal(v,1,x,z,t,u));
    }
    return res;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen(""NAME".inp","r",stdin);
    //freopen(""NAME".out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int u,v;cin>>u>>v;
        if(!union_(u,v))
        {
            A=u;B=v;
        }
        else
        {
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
    }
    memset(dp,-1,sizeof(dp));
    int res=oo;
    res=min({cal(A,0,0,0,0,-1),cal(A,0,0,0,1,-1),cal(A,1,0,1,0,-1),cal(A,1,0,1,1,-1)});
    if(res<oo)cout<<res;
    else cout<<-1;

}
/*
         ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/

Compilation message (stderr)

Main.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main()
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50