oj.uz

Submission #944259

# Submission time Handle Problem Language Result Execution time Memory
944259 2024-03-12T13:06:04 Z LucaIlie Love Polygon (BOI18_polygon) C++17
54 / 100
 143 ms 23588 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
int n;
bool vis[MAX_N + 1], isOnCycle[MAX_N + 1];
int repr[MAX_N + 1], parent[MAX_N + 1], sizee[MAX_N + 1], minChanges[MAX_N + 1][2], dp1[MAX_N + 1], dp2[MAX_N + 1];
vector <int> adj[MAX_N + 1];
unordered_map <string, int> nameToId;

void findCycles( int u, int r ) {
    repr[u] = r;
    for ( int v: adj[u] ) {
        if ( repr[v] == r ) {
            isOnCycle[u] = true;
            return;
        }

        if ( repr[v] == 0 )
            findCycles( v, r );

        if ( isOnCycle[v] ) {
            isOnCycle[u] = true;
            return;
        }
    }
}

void detectCycles() {
    for ( int v = 1; v <= n; v++ )
        vis[v] = false;

    for ( int v = 1; v <= n; v++ ) {
        if ( vis[v] )
            continue;
        findCycles( v, v );
    }
}

void calc( int u ) {
    sizee[u] = 1;
    for ( int v: adj[u] ) {
        if ( isOnCycle[v] )
            continue;

        calc( v );

        minChanges[u][false] += minChanges[v][true];
        sizee[u] += sizee[v];
    }

    minChanges[u][true] = minChanges[u][false] + 1;
    for ( int v: adj[u] ) {
        if ( isOnCycle[v] )
            continue;

        minChanges[u][true] = min( minChanges[u][true], minChanges[u][false] - minChanges[v][true] + minChanges[v][false] + 1 );
    }
}

int main() {
    cin >> n;
    int id = 0;
    for ( int i = 0; i < n; i++ ) {
        string s, t;
        cin >> s >> t;
        nameToId[s] = (nameToId[s] == 0 ? ++id : nameToId[s]);
        nameToId[t] = (nameToId[t] == 0 ? ++id : nameToId[t]);
        parent[nameToId[s]] = nameToId[t];
        adj[nameToId[t]].push_back( nameToId[s] );
    }

    if ( n % 2 == 1 ) {
        cout << -1 << "\n";
        return 0;
    }

    detectCycles();

    for ( int u = 1; u <= n; u++ ) {
        if ( !isOnCycle[u] )
            continue;
        calc( u );
    }

    for ( int v = 1; v <= n; v++ )
        vis[v] = false;
    int ans = 0;
    for ( int v = 1; v <= n; v++ ) {
        if ( !isOnCycle[v] || vis[v] )
            continue;

        vector <int> cycle;
        cycle.push_back( v );
        int u = v;
        do {
            vis[u] = true;
            u = parent[u];
            cycle.push_back( u );
        } while ( u != v );

        if ( cycle.size() == 2 ) {
            ans += minChanges[cycle[0]][true];
            continue;
        }
        if ( cycle.size() == 3 ) {
            ans += minChanges[cycle[0]][false] + minChanges[cycle[1]][false];
            continue;
        }

        dp1[1] = minChanges[cycle[1]][false];
        dp2[1] = minChanges[cycle[1]][true];
        dp1[0] = n;
        for ( int i = 2; i < cycle.size(); i++ ) {
            dp1[i] = min( dp1[i - 1] + minChanges[cycle[i]][true], dp1[i - 2] + minChanges[cycle[i - 1]][false] + minChanges[cycle[i]][false] + 1 );
            dp2[i] = min( dp2[i - 1] + minChanges[cycle[i]][true], dp2[i - 2] + minChanges[cycle[i - 1]][false] + minChanges[cycle[i]][false] + 1 );
        }

        ans += min( dp2[cycle.size() - 1], dp1[cycle.size() - 2] +  minChanges[cycle.back()][false] + minChanges[cycle[1]][false] + 1 );
    }

    cout << ans << "\n";

    return 0;
}

Compilation message

polygon.cpp: In function 'int main()':
polygon.cpp:115:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for ( int i = 2; i < cycle.size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~

Subtask #1
0 / 21.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 119 ms 22532 KB Output is correct
5 Correct 128 ms 16208 KB Output is correct
6 Correct 143 ms 23588 KB Output is correct
7 Correct 98 ms 15812 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15556 KB Output is correct
2 Correct 126 ms 17552 KB Output is correct
3 Correct 95 ms 16320 KB Output is correct
4 Correct 97 ms 14264 KB Output is correct
5 Correct 120 ms 23492 KB Output is correct
6 Correct 108 ms 14784 KB Output is correct
7 Correct 119 ms 14792 KB Output is correct
8 Correct 101 ms 15296 KB Output is correct
9 Correct 99 ms 14276 KB Output is correct
10 Correct 84 ms 13376 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct

Subtask #4
0 / 25.0

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