Submission #1127327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127327		Ludissey	Love Polygon (BOI18_polygon)	C++20	75 / 100	491 ms	42264 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;
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;
    bool b=false;
    for (auto u : neigh3[x])
    {
        if(visited2[u]||u==x) {
            continue;
        }
        visited2[u]=true;
        for (auto v : neigh3[u])
        {
            deg[v]--;
            if(deg[v]==0&&u!=v) leefs.push(v);
        }
        break;
    }
    return;    
}

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]].insert(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;
        }
        for (auto u : neigh3[i]) deg[u]++;
    }
    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