답안 #951573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951573 2024-03-22T06:49:23 Z SaMuEl0516 Love Polygon (BOI18_polygon) C++17
0 / 100
146 ms 33568 KB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<string,int>ht;
vector<int>cnt[(int)1e5+5];
int out[(int)1e5+5],sz[(int)1e5+5];
bool vis[(int)1e5+5];
set<pair<int,int>>se;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,c=0,u,v,ans=0;
    string s,t;
    cin>>n;
    if(n%2){
        cout<<-1;
        return 0;
    }
    for(int i=0;i<n;i++){
        cin>>s>>t;
        if(ht.find(s)!=ht.end())u=ht[s];
        else u=ht[s]=c++;
        if(ht.find(t)!=ht.end())v=ht[t];
        else v=ht[t]=c++;
        out[u]=v;
        if(u==v)continue;
        cnt[u].push_back(v),cnt[v].push_back(u);
        sz[u]++,sz[v]++;
    }
    for(auto p:ht)cout<<p.first<<' '<<p.second<<'\n';
    for(int i=0;i<n;i++){
        if(out[out[i]]==i&&out[i]!=i&&!vis[i]){
            ans+=2,vis[i]=vis[out[i]]=1;
            for(int j:cnt[i])sz[j]--;
        }
    }
    for(int i=0;i<n;i++)se.insert({sz[i],i});
    while(se.size()){
        auto p=*se.begin();
        se.erase(se.begin());
        if(p.first==0||vis[p.second])continue;
        for(int i:cnt[p.second]){
            if(!vis[i]){
                vis[p.second]=vis[i]=1;
                for(int j:cnt[p.second]){
                    if(!vis[j]){
                        se.erase({sz[j],j});
                        sz[j]--;
                        se.insert({sz[j],j});
                    }
                }
                for(int j:cnt[i]){
                    if(!vis[j]){
                        se.erase({sz[j],j});
                        sz[j]--;
                        se.insert({sz[j],j});
                    }
                }
                ans++;
                break;
            }
        }
    }
    cout<<n-ans;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 146 ms 33568 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -