Submission #923718

#	Time	Username	Problem	Language	Result	Execution time	Memory
923718		TahirAliyev	Love Polygon (BOI18_polygon)	C++17	29 / 100	260 ms	38224 KiB

polygon

#include <bits/stdc++.h>

#define ll long long
using namespace std;
#define pii pair<ll, ll>
ll oo = 1e9 + 9;
int n, m, k;
const int MAX = 4e5 + 5, MOD = 1e9 + 7, LOGMAX = 25;

vector<int> g[MAX];
map<string, int> mp;
int par[MAX];
bool vis[MAX];
int sub[MAX];


int dp[MAX][2];

void dfs(int node, int p){
    sub[node] = 1;
    vis[node] = 1;
    int sum = 0;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
        sub[node] += sub[to];
        sum += dp[to][0];
    }
    dp[node][1] = sum + 1;
    for(int to : g[node]){
        if(p == to) continue;
        dp[node][0] = max(dp[to][1] + (sum - dp[to][0]), dp[node][0]);
    }
}

void solve(){
    cin >> n;
    int c = 1;
    for(int i = 1; i <= n; i++){
        string a, b; cin >> a >> b;
        if(!mp[a]) mp[a] = c++;
        if(!mp[b]) mp[b] = c++;
        g[mp[b]].push_back(mp[a]);
        par[mp[a]] = mp[b];
    }
    if(n & 1){
        cout << "-1\n";
        return;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(par[i] == i){
            dfs(i, i);
            ans += sub[i] - dp[i][0];
        }
    }
    cout << ans << '\n';
}

signed main(){
    int t = 1;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

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