oj.uz

Submission #558642

# Submission time Handle Problem Language Result Execution time Memory
558642 2022-05-07T19:13:18 Z Mahmudul_Kabir Love Polygon (BOI18_polygon) C++14
54 / 100
 204 ms 13592 KB 
/*
    
    Note        :            
 
    Link        :       
 
    Boka hoye gelum...
*/
 
#include "bits/stdc++.h"
 
#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define pb push_back
#define all(ar) ar.begin(),ar.end() 
#define pii pair<ll,ll> 
 
 
using namespace std;
using ll = long long;
using ld = long double;
 
const ll mod = 1000000007;
const ll oo = 3372036000000000;
const ll si = 100005;
 
int cru[si], phead = -1,tin[si], psi = 0;
bool done[si], pol[si],vis[si];  
map<string,int> rec; 
vector<int> tps,head; 
int ans = 0; 

void dfs(int v,int tim){
    if(tin[v] == tim){
        phead = v; 
        return; 
    }
    tin[v] = tim; 
    if(cru[v] != v && (tin[cru[v]] == -1 || tin[cru[v]] == tim)) dfs(cru[v], tim); 
    if(phead != -1){
        pol[v] = 1;
        psi++; 
    } 
    if(phead == v){
        phead = -1; 
        head.pb(v);  
    }
    return; 
}

void top_sort(int v){
    vis[v] = 1; 
    if(!vis[cru[v]]) top_sort(cru[v]); 
    tps.pb(v); 
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /*
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
//*/ 
    int n,cur = 0; cin>>n; 
    memset(done,false,sizeof(done)); 
    for(int i = 0; i < n; i++){
        string a,b; cin>>a>>b; 
        if(!rec.count(a)) rec[a] = cur++; 
        if(!rec.count(b)) rec[b] = cur++; 
        cru[rec[a]] = rec[b];
    }
    if(n % 2){
        cout<<-1 el; return 0; 
    }
    for(int i = 0; i < n; i++){
        int des = cru[i]; 
        if(i != des && cru[des] == i){
            done[i] = done[des] = 1; 
        }
    }
    memset(vis,0,sizeof(vis)); 
    for(int i = 0; i < n; i++) if(!vis[i] && !done[i]) top_sort(i); 
    reverse(all(tps)); 
    memset(tin,-1,sizeof(tin)); 
    memset(pol,0,sizeof(pol));  
    for(int i: tps) if(!done[i] && tin[i] == -1) dfs(i,i); 
    for(int i: tps) if(!done[i] && cru[i] != i && !pol[i] && !done[cru[i]]){
        done[i] = done[cru[i]] = 1; 
        ans += 1; 
    }
    for(int x: head){
        psi = 0; bool xe = 1; 
        vector<int> mamu; 
        for(int r = x; r != x || xe ; r = cru[r]){
            xe = 0; 
            psi++; 
            mamu.pb(r); 
        }
        if(psi % 2 == 0){
            ans += psi/2; 
            for(int r: mamu) done[r] = 1; 
        }
    }
    for(int i: tps) if(!done[i] && cru[i] != i && !done[cru[i]]){
        done[i] = done[cru[i]] = 1; 
        ans += 1;   
    }
    for(int i: tps) if(!done[i]) ans += 1; 
    cout<<ans el; 
    return 0;
}
/*
    check for: 
        *missed a break, continue ? 
        *corner cases, n = 1?
        *overflow.
        *unnecessary logics.
        *impreciseness caused by double or long double. 
 
*/

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Incorrect 1 ms 972 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 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 192 ms 13144 KB Output is correct
5 Correct 177 ms 9744 KB Output is correct
6 Correct 204 ms 13592 KB Output is correct
7 Correct 160 ms 8724 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 9824 KB Output is correct
2 Correct 180 ms 10444 KB Output is correct
3 Correct 173 ms 9844 KB Output is correct
4 Correct 158 ms 8804 KB Output is correct
5 Correct 173 ms 12748 KB Output is correct
6 Correct 174 ms 9772 KB Output is correct
7 Correct 181 ms 9820 KB Output is correct
8 Correct 192 ms 9804 KB Output is correct
9 Correct 158 ms 9932 KB Output is correct
10 Correct 139 ms 9924 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 980 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Incorrect 1 ms 972 KB Output isn't correct
9 Halted 0 ms 0 KB -