Submission #1127325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127325		Ludissey	Love Polygon (BOI18_polygon)	C++20	75 / 100	436 ms	33492 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<int> neigh3;
vector<int> visited;
vector<int> visited2;
queue<int> leefs;
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){
    rst++;
    visited2[x]=true;
    if(visited2[neigh3[x]]||neigh3[x]==x) {
        return;
    }
    visited2[neigh3[x]]=true;
    deg[neigh3[neigh3[x]]]--;
    if(deg[neigh3[neigh3[x]]]==0&&neigh3[x]!=neigh3[neigh3[x]]) leefs.push(neigh3[neigh3[x]]);
}

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;
    map<string,int> mp2;
    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]=mp2[sa]=t++;
        }
        if(mp.find(b)==mp.end()) {
            //cerr << b << " " << t <<"\n";
            mp[b]=mp2[b]=t++;

        }
        neigh[mp[sa]]=mp[b];
        neigh2[mp[b]].push_back(mp[sa]);
        while(mp[sa]!=mp2[sa]||mp2[b]!=mp2[b]) {

        }
    }
    
    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(sz(compo));
    for (int i = 0; i < n; i++)  
    {
        neigh3[compoINDEX[i]]=compoINDEX[neigh[i]];
    }
    for (int i = 0; i < sz(compo); i++)  
    {
        if(sz(compo[i])%2==0){
            visited2[i]=1;
            if(sz(compo[i])>2) rst+=sz(compo[i])/2;
        }else{
            rst+=(sz(compo[i])-1)/2;
        }
        deg[neigh3[i]]++;
    }
    for (int i = 0; i < sz(compo); i++)  
    {
        if(deg[i]==0) leefs.push(i);
    }
    while(!leefs.empty())
    {
        int u=leefs.front(); leefs.pop();
        if(visited2[u]) continue;
        dfs3(u);
    }
    for (int i = 0; i < sz(compo); i++)  
    {
        if(!visited2[i]) rst++;
    }
    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