Submission #1127407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127407		Ludissey	Love Polygon (BOI18_polygon)	C++20	75 / 100	287 ms	30104 KiB

polygon

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> a;
vector<int> req;
vector<int> deg;
int n; 

vector<int> neigh;
vector<vector<int>> neigh2;
vector<set<int>> neigh3;
vector<int> visited;
vector<int> visited2;
queue<int> leefs;
queue<int> att;
int rst=0;

vector<vector<int>> compo;
vector<int> compoINDEX;
vector<int> topo;

void dfs(int x){
    visited[x]=1;
    if(!visited[neigh[x]]) dfs(neigh[x]);
    topo.push_back(x);
}

void dfs2(int x){
    if(visited[x]==2) return;
    visited[x]=2;
    compo.back().push_back(x);
    compoINDEX[x]=sz(compo)-1;
    for (auto u : neigh2[x])
    {
        dfs2(u);
    }
}

void dfs3(int x){
    visited[x]=true;
    rst++;
    if(visited[neigh[x]]||neigh[x]==x) return;
    visited[neigh[x]]=true;
    deg[neigh[neigh[x]]]--;
    if(deg[neigh[neigh[x]]]==0&&neigh[x]!=neigh[neigh[x]]) leefs.push(neigh[neigh[x]]);
    return;    
}

void dfs4(int x){
    visited[x]=true;
    rst++;
    if(visited[neigh[x]]||neigh[x]==x) return;
    visited[neigh[x]]=true;
    deg[neigh[neigh[x]]]--;
    if(deg[neigh[neigh[x]]]==0&&neigh[x]!=neigh[neigh[x]]) leefs.push(neigh[neigh[x]]);
    return;    
}

int dfs5(int x){
    visited[x]=true;
    if(visited[neigh[x]]||x==neigh[x]) {
        return 1;
    }
    return dfs5(neigh[x])+1;
}



signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    neigh.resize(n);
    neigh2.resize(n);
    deg.resize(n);
    compoINDEX.resize(n);
    visited.resize(n);
    map<string,int> mp;
    int t=0;
    for (int i = 0; i < n; i++)
    {
        string sa; string b; cin >> sa >> b;
        if(mp.find(sa)==mp.end()){
             //cerr << sa << " " << t<< "\n";
             mp[sa]=t++;
        }
        if(mp.find(b)==mp.end()) {
            //cerr << b << " " << t <<"\n";
            mp[b]=t++;

        }
        neigh[mp[sa]]=mp[b];
        neigh2[mp[b]].push_back(mp[sa]);
    }
    
    for (int i = 0; i < n; i++)  
    {
        if(visited[i]==0) dfs(i);
    }
    for (int i = n-1; i >= 0; i--)  
    {
        if(visited[topo[i]]==2) continue;
        compo.push_back({});
        dfs2(topo[i]);
    }
    
    neigh3.resize(sz(compo));
    visited2.resize(n);
    for (int i = 0; i < n; i++) visited[i]=false;
    
    for (int i = 0; i < sz(compo); i++)  
    {
        if(sz(compo[i])>2) {
            for (int j = 0; j < sz(compo[i]); j++) visited2[compo[i][j]]=1;
        }else if(sz(compo[i])==2) {
            for (int j = 0; j < sz(compo[i]); j++) visited[compo[i][j]]=1;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if(visited2[neigh[i]]==1&&visited2[i]!=1) visited2[i]=2;
        deg[neigh[i]]++;        
    }
    for (int i = 0; i < n; i++) {
        if(deg[i]==0) leefs.push(i);        
    }  

    while(!leefs.empty())
    {
        int u=leefs.front(); leefs.pop();
        if(visited2[u]>0||visited[u]) continue;
        dfs3(u);
    }
    for (int i = 0; i < n; i++)  
    {
        if(!visited[i]&&visited2[i]==2&&visited[neigh[i]]==0) {
            visited[neigh[i]]=true;
            visited[i]=true;
            rst++;
        }
        else if(!visited[i]&&visited2[i]!=1) { visited[i]=true; rst++; }
    }
   
    for (int i = 0; i < n; i++) {
        if(visited[i]) continue;
        deg[neigh[i]]++;        
    }
    for (int i = 0; i < n; i++) {
        if(deg[i]==0) leefs.push(i);        
    }
    while(!leefs.empty())
    {
        int u=leefs.front(); leefs.pop();
        if(visited[u]) continue;
        dfs4(u);
    }
    for (int i = 0; i < n; i++)  
    {
        if(visited[i]) continue;
        rst+=(dfs5(i)+1)/2;
    }

   if(n%2) cout << -1 << "\n";
    else cout << rst << "\n";

    return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 0 / 25