結果

問題 No.1795 AtCoder Heuristic Rating coloring
ユーザー 👑 AngrySadEightAngrySadEight
提出日時 2021-12-25 17:29:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 346 ms / 2,000 ms
コード長 17,413 bytes
コンパイル時間 2,604 ms
コンパイル使用メモリ 201,564 KB
実行使用メモリ 22,528 KB
最終ジャッジ日時 2024-09-21 20:13:07
合計ジャッジ時間 10,977 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(), v.end()
#define mod1 1000000007
#define mod2 998244353
typedef long long ll;
vector<ll> bitconversion(ll i, ll n, ll N)
{
//inN
//bitconversion(33,3,4)={1,0,2,0}
ll x = 1;
rep(j, N)
{
x *= n;
}
vector<ll> vec(N);
rep(j, N)
{
x /= n;
vec[j] = i / x;
i -= x * vec[j];
}
return vec;
}
int ctoi(char c)
{
//char1int
switch (c)
{
case '0':
return 0;
case '1':
return 1;
case '2':
return 2;
case '3':
return 3;
case '4':
return 4;
case '5':
return 5;
case '6':
return 6;
case '7':
return 7;
case '8':
return 8;
case '9':
return 9;
default:
return 0;
}
}
vector<int> topological_sort(vector<vector<int>> &connection, vector<int> &count, int N)
{
//vector
//connection
//count
vector<int> ans(0);
queue<int> que;
for (int i = 0; i < N; i++)
{
if (count[i] == 0)
{
que.push(i);
}
}
while (que.size() != 0)
{
int v = que.front();
que.pop();
for (int i = 0; i < connection[v].size(); i++)
{
count[connection[v][i]] -= 1;
if (count[connection[v][i]] == 0)
{
que.push(connection[v][i]);
}
}
ans.push_back(v);
}
return ans;
}
struct union_find
{
vector<int> par;
vector<int> rank;
vector<int> siz;
vector<int> siz2;
union_find(int N) : par(N), rank(N), siz(N), siz2(N)
{
rep(i, N)
{
par[i] = i;
rank[i] = 0;
siz[i] = 1;
siz2[i] = 0;
}
}
//union_findunion_find tree(N)
int root(int x)
{
if (par[x] == x)
{
return x;
}
return par[x] = root(par[x]);
}
//
void unite(int x, int y)
{
int rx = root(x);
int ry = root(y);
if (rx == ry)
{
siz2[rx]++;
return;
}
if (rank[rx] < rank[ry])
{
par[rx] = ry;
siz[ry] += siz[rx];
siz2[ry] += siz2[rx];
siz2[ry]++;
}
else
{
par[ry] = rx;
siz[rx] += siz[ry];
siz2[rx] += siz2[ry];
siz2[rx]++;
if (rank[rx] == rank[ry])
rank[rx]++;
}
}
//xy(rank)
//
bool same(int x, int y)
{
int rx = root(x);
int ry = root(y);
return rx == ry;
}
//xy
int size(int x)
{
return siz[root(x)];
}
//x
int size2(int x)
{
return siz2[root(x)];
}
};
ll gcd(ll a, ll b)
{
//ab
ll r, temp;
if (a < b)
{
temp = a;
a = b;
b = temp;
}
while ((r = a % b) != 0)
{
a = b;
b = r;
}
return b;
}
ll iterative_square_method(ll i, vector<ll> &vec, ll N, ll mod)
{
//iXmod
//XmoddividingNvector(vec)
//2100000mod1e9+7
//iterative_square_method(2,moddividing(100000,2,30),30,1000000007)
ll ans = 1;
rep(j, N)
{
if (vec[N - 1 - j] == 1)
ans = (ans * i) % mod;
i = (i * i) % mod;
}
return ans;
}
double iterative_square_method2(double X, vector<ll> &vec, ll N)
{
double ans = 1;
rep(j, N)
{
if (vec[N - 1 - j] == 1)
ans = ans * X;
X = X * X;
}
return ans;
}
ll moddividing(ll x, ll y)
{
//x÷ymod1e9+7
vector<ll> vec(30);
rep(i, 30)
{
vec[i] = y;
y = y * y % 1000000007;
}
ll c = x;
c = c * vec[0] % 1000000007;
c = c * vec[2] % 1000000007;
c = c * vec[9] % 1000000007;
c = c * vec[11] % 1000000007;
c = c * vec[14] % 1000000007;
c = c * vec[15] % 1000000007;
c = c * vec[17] % 1000000007;
c = c * vec[19] % 1000000007;
c = c * vec[20] % 1000000007;
c = c * vec[23] % 1000000007;
c = c * vec[24] % 1000000007;
c = c * vec[25] % 1000000007;
c = c * vec[27] % 1000000007;
c = c * vec[28] % 1000000007;
c = c * vec[29] % 1000000007;
return c;
}
ll moddividing2(ll x, ll y)
{
//x÷ymod998244353
vector<ll> vec(30);
rep(i, 30)
{
vec[i] = y;
y = y * y % 998244353;
}
ll c = x;
c = c * vec[0] % 998244353;
c = c * vec[1] % 998244353;
c = c * vec[2] % 998244353;
c = c * vec[3] % 998244353;
c = c * vec[4] % 998244353;
c = c * vec[5] % 998244353;
c = c * vec[6] % 998244353;
c = c * vec[7] % 998244353;
c = c * vec[8] % 998244353;
c = c * vec[9] % 998244353;
c = c * vec[10] % 998244353;
c = c * vec[11] % 998244353;
c = c * vec[12] % 998244353;
c = c * vec[13] % 998244353;
c = c * vec[14] % 998244353;
c = c * vec[15] % 998244353;
c = c * vec[16] % 998244353;
c = c * vec[17] % 998244353;
c = c * vec[18] % 998244353;
c = c * vec[19] % 998244353;
c = c * vec[20] % 998244353;
c = c * vec[21] % 998244353;
c = c * vec[22] % 998244353;
c = c * vec[24] % 998244353;
c = c * vec[25] % 998244353;
c = c * vec[27] % 998244353;
c = c * vec[28] % 998244353;
c = c * vec[29] % 998244353;
return c;
}
struct segtree
{
//
vector<ll> vec;
segtree(ll N) : vec(N)
{
rep(i, N)
{
vec[i] = 0;
}
}
//vector
//N*22
void make(ll k, ll a, ll N)
{ //0_indexed
k += (N / 2);
vec[k] = a;
}
//ka
void sum_update(ll k, ll a, ll N)
{ //0_indexed
k += (N / 2);
vec[k] = a;
while (k > 1)
{
k = k / 2;
vec[k] = vec[k * 2] + vec[k * 2 + 1];
}
}
//ka
void max_update(ll k, ll a, ll N)
{ //0_indexed
k += (N / 2);
vec[k] = a;
while (k > 1)
{
k = k / 2;
vec[k] = max(vec[k * 2], vec[k * 2 + 1]);
}
}
//ka
void min_update(ll k, ll a, ll N)
{ //0_indexed
k += (N / 2);
vec[k] = a;
while (k > 1)
{
k = k / 2;
vec[k] = min(vec[k * 2], vec[k * 2 + 1]);
}
}
//ka
ll min_query(ll a, ll b, ll k, ll l, ll r)
{ // min_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
if (r <= a || b <= l)
return 1000000000;
if (a <= l && r <= b)
return vec[k];
ll vl = min_query(a, b, k * 2, l, (l + r) / 2);
ll vr = min_query(a, b, k * 2 + 1, (l + r) / 2, r);
return min(vl, vr);
}
//[a,b)(a,b0_indexed)
//k,l,rk=1,l=0,r=N/2
ll check(ll i, ll N)
{
return vec[i + N / 2];
}
//i
ll max_query(ll a, ll b, ll k, ll l, ll r)
{ // max_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
if (r <= a || b <= l)
return -100000000000000000;
if (a <= l && r <= b)
return vec[k];
ll vl = max_query(a, b, k * 2, l, (l + r) / 2);
ll vr = max_query(a, b, k * 2 + 1, (l + r) / 2, r);
return max(vl, vr);
}
//[a,b)(a,b0_indexed)
//k,l,rk=1,l=0,r=N/2
ll sum_query(ll a, ll b, ll k, ll l, ll r)
{ // sum_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
if (r <= a || b <= l)
return 0;
if (a <= l && r <= b)
return vec[k];
ll vl = sum_query(a, b, k * 2, l, (l + r) / 2);
ll vr = sum_query(a, b, k * 2 + 1, (l + r) / 2, r);
return vl + vr;
}
//[a,b)(a,b0_indexed)
//k,l,rk=1,l=0,r=N/2
};
char itoc(int c)
{
//int025c(c+1)char1
switch (c)
{
case 0:
return 'a';
case 1:
return 'b';
case 2:
return 'c';
case 3:
return 'd';
case 4:
return 'e';
case 5:
return 'f';
case 6:
return 'g';
case 7:
return 'h';
case 8:
return 'i';
case 9:
return 'j';
case 10:
return 'k';
case 11:
return 'l';
case 12:
return 'm';
case 13:
return 'n';
case 14:
return 'o';
case 15:
return 'p';
case 16:
return 'q';
case 17:
return 'r';
case 18:
return 's';
case 19:
return 't';
case 20:
return 'u';
case 21:
return 'v';
case 22:
return 'w';
case 23:
return 'x';
case 24:
return 'y';
case 25:
return 'z';
default:
return 'a';
}
}
ll kruskal(vector<pair<ll, pair<int, int>>> &connect, union_find tree)
{
//12
//
//connect12
ll ans = 0;
for (ll i = 0; i < connect.size(); i++)
{
if (!tree.same(connect[i].second.first, connect[i].second.second))
{
ans += connect[i].first;
tree.unite(connect[i].second.first, connect[i].second.second);
}
}
return ans;
}
void dijkstra(vector<vector<pair<ll, ll>>> &G, ll s, vector<ll> &dis)
{
//s
//G
//N
//EVO(ElogV
//priority_queue
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pque;
dis[s] = 0;
pque.push(pair<ll, ll>(dis[s], s));
while (!pque.empty())
{
pair<ll, ll> p = pque.top();
pque.pop();
ll v = p.second;
if (dis[v] < p.first)
continue;
for (int i = 0; i < G[v].size(); i++)
{
if (dis[G[v][i].first] > dis[v] + G[v][i].second)
{
dis[G[v][i].first] = dis[v] + G[v][i].second;
pque.push(pair<ll, ll>(dis[G[v][i].first], G[v][i].first));
}
}
}
}
vector<vector<ll>> matrix_exponentiation(vector<vector<ll>> &M, vector<ll> &bin, ll N, ll K, ll mod)
{
//N*NMXXbitconversion2bin
//NMKbinmodmod
vector<vector<ll>> matrix(N, vector<ll>(N));
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
matrix[i][j] = M[i][j];
}
}
vector<vector<ll>> ans_old_matrix(N, vector<ll>(N));
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
if (i == j)
ans_old_matrix[i][j] = 1;
else
ans_old_matrix[i][j] = 0;
}
}
vector<vector<ll>> ans_new_matrix(N, vector<ll>(N));
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
ans_new_matrix[i][j] = 0;
}
}
vector<vector<ll>> new_matrix(N, vector<ll>(N));
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
new_matrix[i][j] = 0;
}
}
for (ll x = 0; x < K; x++)
{
if (bin[K - 1 - x] == 1)
{
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
for (ll k = 0; k < N; k++)
{
ans_new_matrix[i][j] = (ans_new_matrix[i][j] + (ans_old_matrix[i][k] * matrix[k][j])) % mod;
}
}
}
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
ans_old_matrix[i][j] = ans_new_matrix[i][j];
ans_new_matrix[i][j] = 0;
}
}
}
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
for (ll k = 0; k < N; k++)
{
new_matrix[i][j] = (new_matrix[i][j] + (matrix[i][k] * matrix[k][j])) % mod;
}
}
}
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < N; j++)
{
matrix[i][j] = new_matrix[i][j];
new_matrix[i][j] = 0;
}
}
}
return ans_old_matrix;
}
void bellman_ford(vector<ll> &from, vector<ll> &to, vector<ll> &cost, vector<ll> &dis, ll v, ll N, ll M, bool &negative)
{
//
//fromtocostMN
//vdis
//negativetrue
vector<bool> hasroute(N, false);
hasroute[v] = true;
vector<bool> nega(N, false);
for (ll i = 0; i < N; i++)
{
bool update = false;
for (ll j = 0; j < M; j++)
{
if (dis[to[j]] > dis[from[j]] + cost[j])
{
dis[to[j]] = dis[from[j]] + cost[j];
if (hasroute[from[j]])
hasroute[to[j]] = true;
update = true;
if (i == N - 1)
{
nega[to[j]] = true;
}
}
}
if (!update)
{
break;
}
}
for (ll i = 0; i < N; i++)
{
for (ll j = 0; j < M; j++)
{
if (hasroute[from[j]] && nega[from[j]])
nega[to[j]] = true;
}
}
if (hasroute[N - 1] && nega[N - 1])
negative = true;
}
int main()
{
int N, M;
cin >> N >> M;
vector<string> S(N);
vector<int> A(N);
vector<string> T(M);
vector<int> B(M);
rep(i, N) cin >> S[i] >> A[i];
rep(i, M) cin >> T[i] >> B[i];
map<string, int> mp;
for (int i = 0; i < N; i++)
{
mp[S[i]] = A[i];
}
for (int i = 0; i < M; i++)
{
int x = mp[T[i]];
if (B[i] > x)
mp[T[i]] = B[i];
}
for (auto itr = mp.begin(); itr != mp.end(); itr++)
{
cout << itr->first << " " << itr->second << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0