Submission #483022

#	Time	Username	Problem	Language	Result	Execution time	Memory
483022		DJeniUp	Love Polygon (BOI18_polygon)	C++17	100 / 100	197 ms	20796 KiB

polygon

#pragma GCC Optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll n,d[100007],res,f[100007],a[100007];

map<string,ll>m;

string s1[100007],s2[100007];

priority_queue<pairll, vector<pairll>, greater<pairll> >q;

int main() {
    
    cin>>n;
    
    for(int i=1;i<=n;i++){
        cin>>s1[i]>>s2[i];
        m[s1[i]]=i;
    }
    if(n%2==1){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        d[i]=m[s2[i]];
        if(d[i]!=i)a[d[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(d[d[i]]==i && d[i]!=i){
            f[i]=1;
        }else q.push({a[i],i});
    }
    while(q.size()>0){
        ll m1=q.top().fr;
        ll m2=q.top().sc;
        q.pop();
        if(f[m2]==0){
            f[m2]=1;
            if(d[m2]==m2){
                res++;
            }else{
                ll m3=d[m2];
                if(f[m3]==1){
                    res++;
                }else{
                    ll m4=d[m3];
                    res++;
                    a[m4]--;
                    f[m3]=1;
                    q.push({a[m4],m4});
                }
            }
        }
    }
    cout<<res<<endl;

}

Compilation message (stderr)

polygon.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize("O3")
      | 
polygon.cpp: In function 'int main()':
polygon.cpp:51:12: warning: unused variable 'm1' [-Wunused-variable]
   51 |         ll m1=q.top().fr;
      |            ^~

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