Submission #704021

#	Time	Username	Problem	Language	Result	Execution time	Memory
704021		Username4132	Logičari (COCI21_logicari)	C++14	110 / 110	152 ms	19504 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back

const int MAXN=100010, INF=100000000;
int n, x, y, res[MAXN][2][2];
bool vis[MAXN], gcov, gblue;
vector<int> g[MAXN];

inline int wrap(int v, bool blue, bool cover){
    if(v!=y) return res[v][blue][cover];
    else if((gcov^blue) || (gblue && cover)) return -INF;
    else return res[v][blue][cover||gblue];
}

void cyc(int v, int p){
    vis[v]=true;
    for(auto to:g[v]){
        if(to==p) continue;
        if(vis[to]) x=v, y=to;
        else cyc(to, v);
    }
}

void dfs(int v, int p){
    ll ybl=0, nbl=0;
    for(auto to:g[v]){
        if(to==p) continue;
        dfs(to, v);
        ybl+=wrap(to, 0, 1);
        nbl+=wrap(to, 0, 0);
    }
    res[v][0][1]=max(nbl, (ll)(-INF));
    res[v][1][1]=max(ybl+1, (ll)(-INF));
    ll yy=-INF, nn=-INF;
    for(auto to:g[v]){
        if(to==p) continue;
        ll yyy=ybl-wrap(to, 0, 1)+wrap(to, 1, 1);
        ll nnn=nbl-wrap(to, 0, 0)+wrap(to, 1, 0);
        yy = max(yy, yyy), nn = max(nn, nnn);
    }
    res[v][0][0]=max(nn, (ll)(-INF));
    res[v][1][0]=max(yy+1, (ll)(-INF));
}

int main(){
    scanf("%d", &n);
    forn(i, n){
        int a, b; scanf("%d %d", &a, &b);
        --a, --b;
        g[a].PB(b), g[b].PB(a);
    }
    cyc(0, 0);
    g[x].erase(find(g[x].begin(), g[x].end(), y));
    g[y].erase(find(g[y].begin(), g[y].end(), x));

    int mx=-1;
    forn(i, 4){
        gblue = i>>1, gcov = i&1;
        dfs(x, x);
        mx = max(mx, res[x][gblue][gcov]);
    }

    printf("%d\n", mx);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

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