oj.uz

Submission #891212

# Submission time Handle Problem Language Result Execution time Memory
891212 2023-12-22T12:04:56 Z Dec0Dedd Love Polygon (BOI18_polygon) C++14
46 / 100
 289 ms 19112 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<string, string> pii;
 
const int N = 1e5+10;
const int INF = 1e6;
 
int ind[N], ed[N], n;
 
map<string, int> sc;
set<string> st;
 
bool vis[N];
 
int dfs(int v) {
    vis[v]=true;
    if (vis[ed[v]]) return 1;
    return 1+dfs(ed[v]);
}
 
bool checksub2() {
    for (int i=1; i<=n; ++i) {
        if (ind[i] != 1) return false;
    } return true;
}
 
int solvesub2() {
    // everything's a cycle
    int cnt=0, ans=0;
    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        int sz=dfs(i);
 
        if (sz == 2) continue;
 
        ans+=sz/2;
        if (sz%2) ++cnt;
    } ans+=cnt;
    return ans;
}
 
bool checksub1() {
    return n <= 20;
}
 
int dp[1<<20];
bool vis2[1<<20];
 
int edg(int a, int b) {
    return 2-(ed[a]==b)-(ed[b]==a);
}
 
int ssb1(int msk) {
    if (vis2[msk]) return dp[msk];
    if (msk == 0) return 0;
    vis2[msk]=true, dp[msk]=INF;
 
    vector<int> v;
    for (int i=0; i<n; ++i) {
        if (msk&(1<<i)) v.push_back(i);
    } int sz=v.size();
    for (int i=0; i<sz; ++i) {
        for (int j=i+1; j<sz; ++j) {
            dp[msk]=min(dp[msk], ssb1(msk^(1<<v[i])^(1<<v[j]))+edg(v[i]+1, v[j]+1));
        }
    } return dp[msk];
}
 
int solvesub1() {
    return ssb1((1<<n)-1);
}
 
// no cycles
bool checksub3() {
    return true;
}

int dfss(int v, bool ss) {
    vis[v]=true;
 
    if (ed[v] == v) return 0;
    if (vis[ed[v]]) return 0;
    if (ss) return dfss(ed[v], false);
    return dfss(ed[v], true)+1;
}
 
int solvesub3() {
    memset(vis, false, sizeof(vis));
 
    int res=0;
    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        if (ind[i] == 0) res+=dfss(i, false);
    }
    
    return res+(n-2*res); 
}
 
void solve() {
    cin>>n;
 
    int c=1;
    for (int i=1; i<=n; ++i) {
        string a, b; cin>>a>>b;
        if (st.find(a) == st.end()) sc[a]=c++;
        st.insert(a);
        if (st.find(b) == st.end()) sc[b]=c++;
        st.insert(b);
 
        int ap=sc[a], bp=sc[b];
        ed[ap]=bp;
        ++ind[bp];
    }
 
    if (n%2) {
        cout<<-1<<"\n";
        return;
    }
 
    if (checksub2()) cout<<solvesub2()<<"\n";
    else if (checksub1()) cout<<solvesub1()<<"\n";
    else if (checksub3()) cout<<solvesub3()<<"\n";
    else cout<<-1<<"\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t=1;
    while (t--) solve();
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 5468 KB Output is correct
2 Correct 269 ms 5584 KB Output is correct
3 Correct 248 ms 5580 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 273 ms 5584 KB Output is correct
9 Correct 289 ms 5720 KB Output is correct
10 Correct 256 ms 5576 KB Output is correct
11 Correct 257 ms 5464 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 257 ms 19056 KB Output is correct
5 Correct 262 ms 19028 KB Output is correct
6 Correct 221 ms 18940 KB Output is correct
7 Correct 268 ms 19112 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 18972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 5468 KB Output is correct
2 Correct 269 ms 5584 KB Output is correct
3 Correct 248 ms 5580 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 273 ms 5584 KB Output is correct
9 Correct 289 ms 5720 KB Output is correct
10 Correct 256 ms 5576 KB Output is correct
11 Correct 257 ms 5464 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 257 ms 19056 KB Output is correct
20 Correct 262 ms 19028 KB Output is correct
21 Correct 221 ms 18940 KB Output is correct
22 Correct 268 ms 19112 KB Output is correct
23 Incorrect 214 ms 18972 KB Output isn't correct
24 Halted 0 ms 0 KB -