Submission #443114

#	Time	Username	Problem	Language	Result	Execution time	Memory
443114		ak2006	Mutating DNA (IOI21_dna)	C++17	0 / 100	1589 ms	3084 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
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(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<a.size();i++){
        if (val.Find(i) == i)
            ret += val.sz[val.Find(i)] - 1;
    }
    return ret;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0;i<a.size();i++){
      |                    ~^~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16