oj.uz

Submission #486639

# Submission time Handle Problem Language Result Execution time Memory
486639 2021-11-12T07:58:56 Z FatihSolak Love Polygon (BOI18_polygon) C++17
54 / 100
 357 ms 24772 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]]){
        dfs(edge[v]);
    }
    vis[v] = 2;
}
void dfs2(int v){
    for(auto u:adj[v]){
        if(cycle[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];
        adj[val[t]].push_back(val[s]);
    }
    if(n%2){
        cout << -1 << endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    /*
    for(auto u:val){
        cout << u.first << " " << u.second << endl;
    }*/
    for(int i=1;i<=n;i++){
        if(cycle[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 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;
                }
            }
        }
        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 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5028 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 5020 KB Output is correct
8 Incorrect 3 ms 4940 KB Output isn't correct
9 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 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 263 ms 22324 KB Output is correct
5 Correct 235 ms 19092 KB Output is correct
6 Correct 288 ms 22696 KB Output is correct
7 Correct 292 ms 18464 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 18204 KB Output is correct
2 Correct 314 ms 19832 KB Output is correct
3 Correct 231 ms 19016 KB Output is correct
4 Correct 226 ms 16984 KB Output is correct
5 Correct 292 ms 24772 KB Output is correct
6 Correct 279 ms 17416 KB Output is correct
7 Correct 278 ms 17668 KB Output is correct
8 Correct 248 ms 17888 KB Output is correct
9 Correct 280 ms 16960 KB Output is correct
10 Correct 183 ms 16336 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 4 ms 4940 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5028 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 5020 KB Output is correct
8 Incorrect 3 ms 4940 KB Output isn't correct
9 Halted 0 ms 0 KB -