Submission #944226

#	Time	Username	Problem	Language	Result	Execution time	Memory
944226		LucaIlie	Love Polygon (BOI18_polygon)	C++17	25 / 100	140 ms	24632 KiB

polygon

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
int n;
bool vis[MAX_N + 1], isOnCycle[MAX_N + 1], isUnpaired[MAX_N + 1];
int repr[MAX_N + 1], parent[MAX_N + 1], sizee[MAX_N + 1], dp[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 ) {
    int odd = 0;
    sizee[u] = 1;
    for ( int v: adj[u] ) {
        if ( isOnCycle[v] )
            continue;

        calc( v );

        dp[u] += dp[v];
        sizee[u] += sizee[v];
        if ( sizee[v] % 2 == 1 )
            odd++;
    }
    dp[u] += odd;
}

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] );
        //cout << nameToId[s] << " " << nameToId[t] << "\n";
    }

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

    detectCycles();

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

        calc( u );
        ans += dp[u];
        if ( sizee[u] % 2 == 1 )
            isUnpaired[u] = true;
    }

    for ( int v = 1; v <= n; v++ ) {
        if ( parent[v] != v && isUnpaired[v] ) {
            vector<int> cycle;
            int u = v;
            do {
                cycle.push_back( u );
                u = parent[u];
            } while ( u != v );

            if ( cycle.size() == 2 )
                isUnpaired[cycle[0]] = isUnpaired[cycle[1]] = false;
            if ( cycle.size() <= 2 )
                continue;

            for ( int i = 0; i < cycle.size(); i++ ) {
                if ( isUnpaired[cycle[i]] && isUnpaired[cycle[(i + 1) % cycle.size()]] ) {
                    isUnpaired[cycle[i]] = isUnpaired[cycle[(i + 1) % cycle.size()]] = false;
                    ans++;
                }
            }
        }
    }
    for ( int v = 1; v <= n; v++ ) {
        if ( isUnpaired[parent[v]] )
            ans++;
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 21
• Subtask 2: 25 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25