oj.uz

Submission #106636

# Submission time Handle Problem Language Result Execution time Memory
106636 2019-04-19T10:47:28 Z stefdasca Zamjena (COCI18_zamjena) C++14
70 / 70
 662 ms 14180 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define mod 1000000007
#define fi first
#define se second
using namespace std;
int n;
vector<string>a;
vector<string>b;
map<string, int>mp;
map<int, int>sim;
int nr[50002], nr2[50002];
int xx;
vector<int>v[100002];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // shuffle(permutation.begin(), permutation.end(), rng);
    cin>>n;
    for(int i = 1; i <= n; ++i)
    {
        string x;
        cin >> x;
        a.push_back(x);
        int nrr = 0;
        bool gg = 1;
        if(mp[x])
            continue;
        for(int j = 0; j < x.size(); ++j)
        {
            if(!(x[j] >= '0' && x[j] <= '9'))
                gg = 0;
            nrr = nrr * 10 + (x[j] - '0');
        }
        if(gg)
            nr[i] = nrr;
        else
            mp[x] = ++xx;
    }
    for(int i = 1; i <= n; ++i)
    {
        string x;
        cin >> x;
        b.push_back(x);
        int nrr = 0;
        bool gg = 1;
        if(mp[x])
            continue;
        for(int j = 0; j < x.size(); ++j)
        {
            if(!(x[j] >= '0' && x[j] <= '9'))
                gg = 0;
            nrr = nrr * 10 + (x[j] - '0');
        }
        if(gg)
            nr2[i] = nrr;
        else
            mp[x] = ++xx;
    }
    bool rau = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(a[i-1] == b[i-1])
            continue;
        if(mp[a[i-1]])
            v[mp[a[i-1]]].push_back(i);
        if(mp[b[i-1]])
            v[mp[b[i-1]]].push_back(i);
    }
    for(int i = 1; i <= n; ++i)
        if(nr[i] && nr2[i] && nr[i] != nr2[i])
            rau = 1;
    deque<string>d;
    for(int i = 1; i <= n; ++i)
    {
        if(nr[i] && nr2[i])
            continue;
        if(nr[i] && mp[b[i-1]])
        {
            int val = mp[b[i-1]];
            if(sim[val] && sim[val] != nr[i])
                rau = 1;
            else
                sim[val] = nr[i], d.push_back(b[i-1]);
            continue;
        }
        if(nr2[i] && mp[a[i-1]])
        {
            int val = mp[a[i-1]];
            if(sim[val] && sim[val] != nr2[i])
                rau = 1;
            else
                sim[val] = nr2[i], d.push_back(a[i-1]);
            continue;
        }
        if(sim[mp[a[i-1]]] && sim[mp[b[i-1]]] && sim[mp[a[i-1]]] != sim[mp[b[i-1]]])
        {
            rau = 1;
            continue;
        }
        if(sim[mp[a[i-1]]])
        {
            sim[mp[b[i-1]]] = sim[mp[a[i-1]]];
            d.push_back(b[i-1]);
        }
        if(sim[mp[b[i-1]]])
        {
            sim[mp[a[i-1]]] = sim[mp[b[i-1]]];
            d.push_back(a[i-1]);
        }
    }
    while(!d.empty())
    {
        string p = d[0];
        d.pop_front();
        int val = mp[p];
        for(int j = 0; j < v[val].size(); ++j)
        {
            int pos = v[val][j];
            if(b[pos-1] == p)
            {
                if(!sim[mp[a[pos-1]]])
                    sim[mp[a[pos-1]]] = sim[val], d.push_back(a[pos-1]);
            }
            if(a[pos-1] == p)
            {
                if(!sim[mp[b[pos-1]]])
                    sim[mp[b[pos-1]]] = sim[val], d.push_back(b[pos-1]);
            }
        }
    }
    for(int j = 1; j <= n; ++j)
    {
        if(!sim[mp[a[j-1]]] && !sim[mp[b[j-1]]])
            continue;
        if(!nr[j])
            nr[j] = sim[mp[a[j-1]]];
        if(!nr2[j])
            nr2[j] = sim[mp[b[j-1]]];
        if(nr[j] != nr2[j])
            rau = 1;
    }
    if(rau)
        cout << "NE\n";
    else
        cout << "DA\n";
    return 0;
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < x.size(); ++j)
                        ~~^~~~~~~~~~
zamjena.cpp:51:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < x.size(); ++j)
                        ~~^~~~~~~~~~
zamjena.cpp:119:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < v[val].size(); ++j)
                        ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2816 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct
3 Correct 23 ms 3448 KB Output is correct
4 Correct 29 ms 3456 KB Output is correct
5 Correct 22 ms 3456 KB Output is correct
6 Correct 24 ms 3328 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4564 KB Output is correct
2 Correct 154 ms 6800 KB Output is correct
3 Correct 290 ms 9064 KB Output is correct
4 Correct 407 ms 10856 KB Output is correct
5 Correct 662 ms 14180 KB Output is correct
6 Correct 638 ms 11316 KB Output is correct