oj.uz

Submission #474355

# Submission time Handle Problem Language Result Execution time Memory
474355 2021-09-18T04:46:40 Z Killer2501 Zamjena (COCI18_zamjena) C++14
70 / 70
 88 ms 11852 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5036 KB Output is correct
3 Correct 7 ms 5324 KB Output is correct
4 Correct 7 ms 5452 KB Output is correct
5 Correct 7 ms 5324 KB Output is correct
6 Correct 6 ms 5324 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6092 KB Output is correct
2 Correct 26 ms 7488 KB Output is correct
3 Correct 45 ms 9028 KB Output is correct
4 Correct 55 ms 9968 KB Output is correct
5 Correct 88 ms 11852 KB Output is correct
6 Correct 63 ms 10148 KB Output is correct