oj.uz

Submission #891215

# Submission time Handle Problem Language Result Execution time Memory
891215 2023-12-22T12:21:42 Z Dec0Dedd Love Polygon (BOI18_polygon) C++14
75 / 100
 282 ms 32884 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;
vector<int> GT[N];
 
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;
}

bool usd[N];
int dfss(int v, int p=-1) {
    vis[v]=true;

    int x=0;
    for (auto u : GT[v]) {
        if (vis[u]) continue;
        x+=dfss(u, v);
    }

    if (p != -1 && !usd[v] && !usd[p]) {
        usd[v]=usd[p]=true;
        ++x;
    } return x;
}
 
int solvesub3() {
    memset(vis, false, sizeof(vis));
    memset(usd, false, sizeof(usd));

    int res=0;
    for (int i=1; i<=n; ++i) {
        if (ed[i] != i) continue;
        res+=dfss(i);
    } return n-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;
        GT[bp].push_back(ap);
        ++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 260 ms 8728 KB Output is correct
2 Correct 254 ms 8796 KB Output is correct
3 Correct 250 ms 8724 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 264 ms 8716 KB Output is correct
9 Correct 267 ms 8724 KB Output is correct
10 Correct 254 ms 8720 KB Output is correct
11 Correct 253 ms 8540 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 282 ms 23208 KB Output is correct
5 Correct 224 ms 23168 KB Output is correct
6 Correct 262 ms 23188 KB Output is correct
7 Correct 227 ms 23332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 22484 KB Output is correct
2 Correct 260 ms 26972 KB Output is correct
3 Correct 180 ms 25512 KB Output is correct
4 Correct 218 ms 24020 KB Output is correct
5 Correct 270 ms 32884 KB Output is correct
6 Correct 221 ms 23988 KB Output is correct
7 Correct 226 ms 24180 KB Output is correct
8 Correct 221 ms 24396 KB Output is correct
9 Correct 200 ms 23636 KB Output is correct
10 Correct 148 ms 22764 KB Output is correct
11 Correct 11 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 11 ms 6684 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 8728 KB Output is correct
2 Correct 254 ms 8796 KB Output is correct
3 Correct 250 ms 8724 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 264 ms 8716 KB Output is correct
9 Correct 267 ms 8724 KB Output is correct
10 Correct 254 ms 8720 KB Output is correct
11 Correct 253 ms 8540 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 282 ms 23208 KB Output is correct
20 Correct 224 ms 23168 KB Output is correct
21 Correct 262 ms 23188 KB Output is correct
22 Correct 227 ms 23332 KB Output is correct
23 Correct 230 ms 22484 KB Output is correct
24 Correct 260 ms 26972 KB Output is correct
25 Correct 180 ms 25512 KB Output is correct
26 Correct 218 ms 24020 KB Output is correct
27 Correct 270 ms 32884 KB Output is correct
28 Correct 221 ms 23988 KB Output is correct
29 Correct 226 ms 24180 KB Output is correct
30 Correct 221 ms 24396 KB Output is correct
31 Correct 200 ms 23636 KB Output is correct
32 Correct 148 ms 22764 KB Output is correct
33 Correct 11 ms 6492 KB Output is correct
34 Correct 2 ms 6492 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 11 ms 6684 KB Output is correct
37 Incorrect 233 ms 25168 KB Output isn't correct
38 Halted 0 ms 0 KB -