oj.uz

Submission #486711

# Submission time Handle Problem Language Result Execution time Memory
486711 2021-11-12T13:01:23 Z FatihSolak Love Polygon (BOI18_polygon) C++17
54 / 100
 325 ms 22596 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;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i] && !del[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(cycle[i] && !del[i]){
            dfs2(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(del[i])continue;
        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;
            }
        }
        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 4940 KB Output is correct
3 Correct 3 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 3 ms 4940 KB Output is correct
11 Incorrect 2 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 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 303 ms 20180 KB Output is correct
5 Correct 307 ms 16836 KB Output is correct
6 Correct 308 ms 20580 KB Output is correct
7 Correct 304 ms 16324 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 16216 KB Output is correct
2 Correct 325 ms 17752 KB Output is correct
3 Correct 239 ms 16900 KB Output is correct
4 Correct 262 ms 14788 KB Output is correct
5 Correct 282 ms 22596 KB Output is correct
6 Correct 261 ms 15300 KB Output is correct
7 Correct 282 ms 15364 KB Output is correct
8 Correct 271 ms 15840 KB Output is correct
9 Correct 247 ms 14812 KB Output is correct
10 Correct 194 ms 14120 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 2 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 4940 KB Output is correct
3 Correct 3 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 3 ms 4940 KB Output is correct
11 Incorrect 2 ms 4940 KB Output isn't correct
12 Halted 0 ms 0 KB -