oj.uz

Submission #703938

# Submission time Handle Problem Language Result Execution time Memory
703938 2023-03-01T04:03:37 Z Username4132 Logičari (COCI21_logicari) C++14
10 / 110
 128 ms 19532 KB 
#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=-INF;
    forn(i, 4){
        gblue = i>>1, gcov = i&1;
        dfs(x, x);
        mx = max(mx, res[x][gblue][gcov]);
    }

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

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2660 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 119 ms 19412 KB Output is correct
6 Correct 103 ms 19520 KB Output is correct
7 Correct 128 ms 19532 KB Output is correct
8 Correct 125 ms 19456 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2660 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 119 ms 19412 KB Output is correct
6 Correct 103 ms 19520 KB Output is correct
7 Correct 128 ms 19532 KB Output is correct
8 Correct 125 ms 19456 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Incorrect 2 ms 2644 KB Output isn't correct
12 Halted 0 ms 0 KB -