Submission #746361

#	Time	Username	Problem	Language	Result	Execution time	Memory
746361		gagik_2007	Love Polygon (BOI18_polygon)	C++17	75 / 100	264 ms	30976 KiB

polygon

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int N = 100007;
ll n, m, k;
string name[N];
map<string, int> revname;
vector<int>g[N];
// topological order 
vector<int>order;
bool vis[N];
bool used[N];

void dfs(int u){
    vis[u]=true;
    for(auto v:g[u]){
        if(!vis[v]){
            dfs(v);
        }
    }
    order.push_back(u);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    vector<pair<string,string>>vec;
    for(int i=0;i<n;i++){
        string a,b;
        cin>>a>>b;
        vec.push_back({a,b});
        name[i]=a;
        revname[a]=i;
    }
    if(n%2==1){
        cout<<-1<<endl;
        return 0;
    }
    for(auto e:vec){
        string a=e.ff;
        string b=e.ss;
        int u=revname[a];
        int v=revname[b];
        g[u].push_back(v);
    }
    for(int i=0;i<n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    reverse(order.begin(),order.end());
    for(int v=0;v<n;v++){
        if(g[g[v][0]][0]==v&&g[v][0]!=v){
            used[v]=true;
        }
    }
    int tuzik=0;
    int ans=0;
    for(int v:order){
        if(!used[v]){
            int to=g[v][0];
            if(used[to]){
                tuzik++;
            }
            else{
                ans++;
                used[to]=true;
            }
            used[v]=true;
        }
    }
    cout<<ans+tuzik<<endl;
    return 0;
}

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