Submission #1368419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368419		maya_s	Love Polygon (BOI18_polygon)	C++20	21 / 100	2092 ms	16172 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll SIZE = 100100;
bool info[SIZE];

ll solve(ll n, vector<ll> &edge, vector<vector<ll>> &rg){
    vector<ll> e(n);
    for(ll i = 1; i <= n; i++) e[i-1] = edge[i]-1;
    if(n % 2) return -1;
    vector<bool> bv(n);
    for(ll i = n-1; i >= 0; i--){
        bv[i] = 1;
        sort(bv.begin(), bv.end());
        do{
            vector<ll> ind(n), outd(n);
            ll cnt = 0;
            for(ll j = 0; j < n; j++) {
                if(bv[j]) cnt++;
                else ind[e[j]]++, outd[j]++;
            }
            bool lol = 1;
            for(ll j = 0; j < n; j++){
                if(ind[j] + outd[j] > 1){
                    if(!(ind[j] == 1 && outd[j] == 1 && e[e[j]] == j && e[j] != j)) lol = 0;
                }
            }
            if(lol) return cnt;
        }
        while(next_permutation(bv.begin(), bv.end()));
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n, cnt = 0; cin >> n;
    vector<ll> edge(n+1);
    vector<vector<ll>> rg(n+1);
    map<string, ll> names;
    for(ll i = 0; i < n; i++){
        string s, t; cin >> s >> t;
        if(!names[s]) names[s] = ++cnt;
        if(!names[t]) names[t] = ++cnt;
        edge[names[s]] = names[t]; rg[names[t]].push_back(names[s]);
    }
    cout << solve(n, edge, rg);
}

Compilation message (stderr)

polygon.cpp: In function 'll solve(ll, std::vector<long long int>&, std::vector<std::vector<long long int> >&)':
polygon.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
   32 | }
      | ^

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