Submission #376949

#	Time	Username	Problem	Language	Result	Execution time	Memory
376949		AriaH	Love Polygon (BOI18_polygon)	C++11	29 / 100	383 ms	43884 KiB

polygon

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

char C[N];

string ask()
{
	scanf("%s", C);
	string s = C;
	return s;
}

int n, mark[N], dp[2][N]; /// dp[0][v] -> v match shode bashe
						  /// dp[1][v] -> v match nashode bashe

map < string , int > mp;

vector < int > G[N], roots;

void dfs(int v)
{
	mark[v] = 1;
	for(auto u : G[v])
	{
		if(mark[u]) continue;
		dfs(u);
		dp[0][v] = max(dp[0][v] + max(dp[0][u], dp[1][u]), dp[1][v] + dp[1][u] + 1);
		dp[1][v] = dp[1][v] + max(dp[0][u], dp[1][u]);
	}
}

int main()
{
	scanf("%d", &n);
	if(n & 1)
	{
		return !printf("-1");
	}
	int cnt = 0;
	for(int i = 1; i <= n; i ++)
	{
		string s = ask(), t = ask();
		if(mp.count(s) == 0) mp[s] = ++ cnt;
		if(mp.count(t) == 0) mp[t] = ++ cnt;
		if(mp[s] == mp[t]) { roots.push_back(mp[s]); continue; }
		G[mp[t]].push_back(mp[s]);
	}
	int tot = n;
	for(auto i : roots)
	{
		if(mark[i]) continue;
		dfs(i);
		tot -= max(dp[0][i], dp[1][i]);
	}
	printf("%d\n", tot);
	return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

polygon.cpp: In function 'std::string ask()':
polygon.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%s", C);
      |  ~~~~~^~~~~~~~~
polygon.cpp: In function 'int main()':
polygon.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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