Submission #1218324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218324		Malix	Love Polygon (BOI18_polygon)	C++20	0 / 100	153 ms	8796 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n;
map<string,int> mp;
vi a,arr,vis;

void dfs(int x){
    arr.PB(x);
    vis[x]=1;
    if(!vis[a[x]])dfs(a[x]);
}

int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
    cin>>n;
    a.resize(n);vis.resize(n,0);
    int tmp=1;
    REP(i,0,n){
        string x,y;cin>>x>>y;
        if(mp[x]==0)mp[x]=tmp++;
        if(mp[y]==0)mp[y]=tmp++;
        a[mp[x]-1]=mp[y]-1;
    }
    if(n%2){
        cout<<-1;
        return 0;
    }
    int ans=0;
    REP(i,0,n)if(!vis[i]){
        dfs(i);
        int k=arr.size();
        ans+=k/2+k%2;
        arr.clear();
    }
    cout<<ans;
}

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