Submission #558095

#	Time	Username	Problem	Language	Result	Execution time	Memory
558095		Mahmudul_Kabir	Love Polygon (BOI18_polygon)	C++14	75 / 100	247 ms	14936 KiB

polygon

/*
    
    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];
bool done[si], pol[si],vis[si];  
map<string,int> rec; 
vector<int> tps; 

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; 
    if(phead == v) phead = -1; 
    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)); 
    int ans = 0; 
    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 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: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 0 / 25