oj.uz

Submission #924645

# Submission time Handle Problem Language Result Execution time Memory
924645 2024-02-09T11:10:45 Z TahirAliyev Love Polygon (BOI18_polygon) C++17
54 / 100
 319 ms 37456 KB 
#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]);
    }
}

int p[MAX];
int get(int node){
    if(p[node] < 0) return node;
    return p[node] = get(p[node]);
}
void unite(int u, int v){
    u = get(u);
    v = get(v);
    if(u == v) return;
    if(-p[u] < -p[v]) swap(u, v);
    p[u] += p[v];
    p[v] = u;
}

void solve(){
    memset(p, -1, sizeof(p));
    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++;
        unite(mp[a], mp[b]);
        g[mp[b]].push_back(mp[a]);
        par[mp[a]] = mp[b];
    }
    if(n & 1){
        cout << "-1\n";
        return;
    }
    bool b = 1;
    for(int i = 1; i <= n; i++){
        if(g[i].empty()) b = false;
    }
    if(b){
        int sum = 0;
        for(int i = 1; i <= n; i++){
            if(p[i] < 0 && -p[i] != 2){
                sum += (-p[i] + 1) / 2;
            }
        }
        cout << sum << '\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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15964 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 3 ms 15964 KB Output is correct
4 Incorrect 3 ms 13916 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 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13912 KB Output is correct
4 Correct 308 ms 26932 KB Output is correct
5 Correct 269 ms 26960 KB Output is correct
6 Correct 319 ms 26980 KB Output is correct
7 Correct 275 ms 26812 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 27984 KB Output is correct
2 Correct 289 ms 30476 KB Output is correct
3 Correct 268 ms 24660 KB Output is correct
4 Correct 268 ms 23324 KB Output is correct
5 Correct 274 ms 37456 KB Output is correct
6 Correct 260 ms 27248 KB Output is correct
7 Correct 319 ms 27464 KB Output is correct
8 Correct 263 ms 27740 KB Output is correct
9 Correct 263 ms 27108 KB Output is correct
10 Correct 190 ms 26060 KB Output is correct
11 Correct 3 ms 15964 KB Output is correct
12 Correct 3 ms 15796 KB Output is correct
13 Correct 4 ms 15964 KB Output is correct
14 Correct 3 ms 15964 KB Output is correct

Subtask #4
0 / 25.0

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