| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 443118 | ak2006 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
#define int long long
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
struct DSU
{
int n;
vi p,sz;
DSU(int _n)
{
n = _n;
p.assign(n + 1,-1);
sz.assign(n + 1,1);
for (int i = 0;i<=n;i++)p[i] = i;
}
int Find(int a)
{
if (a == p[a])return a;
return p[a] = Find(p[a]);
}
void Merge(int a,int b)
{
a = Find(a),b = Find(b);
if (a == b)return;
if (sz[a] < sz[b])swap(a,b);
p[b] = a;
sz[a] += sz[b];
}
};
string a,b;
void init(string A, string B) {
a = A;
b = B;
}
int get_distance(int x, int y) {
map<char,vi>pos1,pos2;
for (int i = x;i<=y;i++){
pos1[a[i]].pb(i);
pos2[b[i]].pb(i);
}
if (pos1['A'].size() != pos2['A'].size() or pos1['T'].size() != pos2['T'].size()
or pos1['C'].size() != pos2['C'].size())return -1;
map<char,int>ppos2;
DSU val((int)a.size() + 1);
for (int i = x;i<=y;i++){
val.Merge(i,pos2[a[i]][ppos2[a[i]]]);
ppos2[a[i]]++;
}
int ret = 0;
for (int i = 0;i<(int)a.size();i++){
if (val.Find(i) == i)
ret += val.sz[val.Find(i)] - 1;
}
return ret;
}