oj.uz

Submission #443114

# Submission time Handle Problem Language Result Execution time Memory
443114 2021-07-09T18:03:33 Z ak2006 Mutating DNA (IOI21_dna) C++17
0 / 100
 1500 ms 3084 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 3084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 287 ms 1848 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 287 ms 1848 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 287 ms 1848 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 3084 KB Time limit exceeded
2 Halted 0 ms 0 KB -