Submission #474355

#	Time	Username	Problem	Language	Result	Execution time	Memory
474355		Killer2501	Zamjena (COCI18_zamjena)	C++14	70 / 70	88 ms	11852 KiB

zamjena

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const ll mod = 1e9 + 7;
const int base = 40;
ll n, m, k, t, a[N], b[N], c[N], tong, dp[N], lab[N];
long long ans;
vector<ll> adj[N];
pll p[N];
ll pw(ll k, ll n)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n & 1)total = total * k % mod;
		k = k * k % mod;
	}
	return total;
}
bool ccw(pll x, pll y, pll z)
{
	return x.fi * (y.se - z.se) + y.fi * (z.se - x.se) + z.fi * (x.se - y.se) >= 0;
}
ll C(ll u, ll v)
{
	if(u > v)return 0;
	return a[v] * b[u] % mod * b[v-u] % mod;
}
ll findp(ll u)
{
	return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(ll u, ll v)
{
	if(lab[u] > lab[v])swap(u, v);
	lab[u] += lab[v];
	lab[v] = u;
	if(a[v] && a[u] && a[u] != a[v])ans = 1;
	a[u] = max(a[v], a[u]);
}
map<string, ll> mp;
void sol()
{
	cin >> n;
	fill_n(lab, 4*n+5, -1);
	for(int i = 1; i <= n; i ++)
	{
		string s;
		cin >> s;
        if(s[0] >= 'a' && s[0] <= 'z')
		{
			if(!mp[s])mp[s] = ++m;
			b[i] = n*2 + mp[s];
		}
        else
		{
			b[i] = i;
			reverse(s.begin(), s.end());
			while(!s.empty())
			{
				a[i] = a[i] * 10 + s.back() - '0';
				s.pop_back();
			}
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		string s;
		cin >> s;
        if(s[0] >= 'a' && s[0] <= 'z')
		{
			if(!mp[s])mp[s] = ++m;
			b[i+n] = n*2 + mp[s];
		}
        else
		{
			b[i+n] = i+n;
			reverse(s.begin(), s.end());
			while(!s.empty())
			{
				a[i+n] = a[i+n] * 10 + s.back() - '0';
				s.pop_back();
			}
		}
		//cout << a[i] <<" "<< a[i+n] << '\n';
		ll u = findp(b[i]), v = findp(b[i+n]);
		if(u != v)hop(u, v);
	}
	if(ans)cout << "NE";
	else cout << "DA";
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int test = 1;
    //cin >> test;
    while (test-- > 0)
        sol();
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14