oj.uz

Submission #486703

# Submission time Handle Problem Language Result Execution time Memory
486703 2021-11-12T12:50:59 Z FatihSolak Love Polygon (BOI18_polygon) C++17
54 / 100
 325 ms 22540 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
int ans = 0;
int edge[N];
bool cycle[N];
int vis[N];
bool del[N];
void dfs(int v){
    vis[v] = 1;
    if(vis[edge[v]] == 1){
        cycle[v] = 1;
        int tmp = edge[v];
        while(tmp != v){
            cycle[tmp] = 1;
            tmp = edge[tmp];
        }
    }
    else if(!vis[edge[v]] && !del[edge[v]]){
        dfs(edge[v]);
    }
    vis[v] = 2;
}
void dfs2(int v){
    for(auto u:adj[v]){
        if(cycle[u] || del[u])continue;
        dfs2(u);
        ans += !del[u];
        if(!del[u]){
            del[v] = del[u] = 1;
        }
    }
}
void solve(){
    int n;
    cin >> n;
    int cnt = 1;
    map<string,int>val;
    for(int i=1;i<=n;i++){
        string s,t;
        cin >> s >> t;
        if(!val[s])val[s] = cnt++;
        if(!val[t])val[t] = cnt++;
        edge[val[s]] = val[t];
        if(edge[val[t]] == val[s] && s != t){
            del[val[s]] = 1;
            del[val[t]] = 1;
        }
        adj[val[t]].push_back(val[s]);
    }
    if(n%2){
        cout << -1 << endl;
        return;
    }
    /*
    if(n <= 20){
        int ans = n;
        for(int mask = 0;mask < (1<<(n+1));mask+=2){
            vector<int> go(n+1);
            bool ok = 1;
            for(int i=1;i<=n;i++){
                if(mask & (1<<i)){
                    if(edge[i] == i)ok = 0;
                    if(go[i] && edge[i] != go[i])ok = 0;
                    go[i] = edge[i];
                    if(go[edge[i]] && go[edge[i]] != i)ok = 0;
                    go[edge[i]] = i;
                }
            }
            if(ok)
                ans = min(ans,n - __builtin_popcount(mask));
        }
        cout << ans;
        return;
    }*/
    for(int i=1;i<=n;i++){
        if(!vis[i] && !del[i]){
            dfs(i);
        }
    }
    /*
    for(auto u:val){
        cout << u.first << " " << u.second << endl;
    }*/
    for(int i=1;i<=n;i++){
        if(cycle[i] && !del[i]){
            dfs2(i);
        }
    }
    /*
    for(auto u:val){
        cout << u.first << " " << del[u.second] << endl;
    }*/
    //cout << ans << endl;
    for(int i=1;i<=n;i++){
        if(del[i])continue;
        //cout << i << endl;
        vector<int> v;
        int tmp = i;
        while(v.empty() || tmp != i){
            v.push_back(tmp);
            if(!del[edge[tmp]])
                tmp = edge[tmp];
            else {
                tmp = -1;
                break;
            }
        }
        /*
        cout << "HEY" << endl;
        cout << tmp << endl;
        for(auto u:v){
            cout << u << " ";
        }
        cout << endl;*/
        if(tmp == i){
            if(v.size() != 2){
                ans += v.size()/2 + v.size()%2;
            }
            for(auto u:v)del[u] = 1;
            continue;
        }
        int bef = -1;
        for(auto u:adj[i]){
            if(!del[u])bef = u;
        }
        while(bef != -1){
            v.push_back(bef);
            for(auto u:adj[bef]){
                if(!del[u]){
                    bef = u;
                    break;
                }
            }
            if(bef == v.back())bef = -1;
        }
        for(auto u:v)del[u] = 1;
        ans += v.size()/2 + v.size()%2;
    }
    cout << ans;

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Incorrect 3 ms 4940 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 307 ms 20212 KB Output is correct
5 Correct 315 ms 16960 KB Output is correct
6 Correct 299 ms 20628 KB Output is correct
7 Correct 277 ms 16324 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16164 KB Output is correct
2 Correct 321 ms 17756 KB Output is correct
3 Correct 255 ms 16960 KB Output is correct
4 Correct 312 ms 14912 KB Output is correct
5 Correct 299 ms 22540 KB Output is correct
6 Correct 325 ms 15428 KB Output is correct
7 Correct 308 ms 15432 KB Output is correct
8 Correct 299 ms 15748 KB Output is correct
9 Correct 263 ms 14788 KB Output is correct
10 Correct 208 ms 14084 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Incorrect 3 ms 4940 KB Output isn't correct
12 Halted 0 ms 0 KB -