Submission #1255719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255719		modwwe	Svjetlo (COCI20_svjetlo)	C++20	110 / 110	307 ms	148316 KiB

svjetlo

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)https://loj.ac/s/2349245
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#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) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e9;
const int mod2 = 998244353;
//const ll base=67;
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, 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, dem5, dem6, dem7, dem9, now, root, q, en;
int el = 19;
main()
{
    ///top1apio
    if (fopen(task2".inp", "r"))
    {
        fin(task2);
        fou(task2);
    }

    ///top1apio
    if (fopen(task".inp", "r"))
    {
        fin(task);
        fou(task);
    }

    ///top1apio
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    //   cin>>s1;
    //ll t;cin >> t;while (t--)
    phongbeo();
    ///  checktime
    ///top1apio
}
int dp[500001][2][2][2];
int c[2][2][2];
string s;
int sz[500001];
vector<int> v[500001];
void dfs(int x,int y)
{
    for(auto f:v[x])
        if(f^y)
        {
            dfs(f,x);
            sz[x]+=sz[f];
        }
    int state=s[x-1]-'0';
    dp[x][state][0][0]=0;
    dp[x][1-state][0][1]=1;
    sz[x]+=state;
    for(auto f:v[x])
        if(f^y)
        {
            for(int i=0; i<=1; i++)
                for(int j=0; j<=1; j++)
                    for(int t=0; t<=1; t++)
                    {
                        ///i color x
                        ///j color f
                        ///case1:no root
                        for(int g=0; g<=1; g++)
                        {
                            if(j==1)c[1-i][t][g]=min(c[1-i][t][g],dp[x][i][t][g]+dp[f][j][0][0]+2);
                            else
                            {
                                if(dp[f][j][0][0]==0)c[i][t][g]=min(dp[x][i][t][g],c[i][t][g]);
                                else c[i][t][g]=min(dp[x][i][t][g]+dp[f][j][0][0]+4,c[i][t][g]);
                            }
                        }
                        ///case 2: root and no root but
                        if(t==0)
                        {
                            for(int g=0; g<=1; g++)
                            {
                                if(j==1)c[i][1][g]=min(c[i][1][g],dp[x][i][t][g]+dp[f][j][1][0]+1);
                                else
                                {
                                    c[1-i][1][g]=min(dp[x][i][t][g]+dp[f][j][1][0]+3,c[1-i][1][g]);
                                }
                            }
                        }
                        ///case3: root on f
                        for(int g=0; g<=1-t; g++)
                        {
                            if(g==0)
                            {
                                if(j==1)
                                {
                                    c[i][t][1]=min(c[i][t][1],dp[x][i][t][0]+dp[f][j][g][1]+3);
                                }
                                else
                                {
                                    c[1-i][t][1]=min(c[1-i][t][1],dp[x][i][t][0]+dp[f][j][g][1]+1);
                                }
                            }
                            else
                            {

                                if(j==1)
                                {
                                    c[1-i][g][1]=min(c[1-i][g][1],dp[x][i][t][0]+dp[f][j][g][1]+2);
                                }
                                else
                                {
                                    c[i][g][1]=min(c[i][g][1],dp[x][i][t][0]+dp[f][j][g][1]+4);
                                }
                            }
                        }
                    }
            for(int i=0; i<=1; i++)
                for(int j=0; j<=1; j++)
                    for(int t=0; t<=1; t++)
                    {
                        dp[x][i][j][t]=c[i][j][t];
                        c[i][j][t]=inf;
                    }
        }
    for(int i=0; i<=1; i++)
    {
        dp[x][i][1][1]=min(dp[x][i][0][1],dp[x][i][1][1]);
        dp[x][i][1][0]=min(dp[x][i][0][0],dp[x][i][1][0]);
    }
    if(sz[x]==dem)
    {
        s4=min(s4,dp[x][0][1][1]);
    }
}
void phongbeo()
{
    cin>>n>>s;
    for(int i=1; i<n; i++)
      cin>>l>>r,v[l].pb(r),v[r].pb(l);
    for(int i=1; i<=n; i++)
        for(int j=0; j<2; j++)
            for(int z=0; z<2; z++)
                for(int t=0; t<2; t++){
                    dp[i][j][z][t]=inf;
                    c[j][z][t]=inf;
                }
    for(int i=0; i<n; i++)
        if(s[i]=='0')s[i]='1',dem++;
        else s[i]='0';
        s4=inf;
    dfs(1,0);
    cout<<s4;

}

Compilation message (stderr)

svjetlo.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~
svjetlo.cpp: In function 'int main()':
svjetlo.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
svjetlo.cpp:38:9: note: in expansion of macro 'fin'
   38 |         fin(task2);
      |         ^~~
svjetlo.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
svjetlo.cpp:39:9: note: in expansion of macro 'fou'
   39 |         fou(task2);
      |         ^~~
svjetlo.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
svjetlo.cpp:45:9: note: in expansion of macro 'fin'
   45 |         fin(task);
      |         ^~~
svjetlo.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)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
svjetlo.cpp:46:9: note: in expansion of macro 'fou'
   46 |         fou(task);
      |         ^~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30