oj.uz

Submission #846138

# Submission time Handle Problem Language Result Execution time Memory
846138 2023-09-07T11:33:16 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 82 ms 22096 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

struct DSU
{
    vector <int> par;
    DSU(int n)
    {
        par.resize(n);
        iota(par.begin(), par.end(), 0ll);
    }

    inline int get(int a)
    {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }

    bool same(int u, int v)
    {
        return get(u) == get(v);
    }

    bool unite(int u, int v)
    {
        if(same(u, v)) return false;
        u = get(u), v = get(v);

        par[v] = u;
        return true;
    }
};

void solve()
{
    int n, m, v; cin >> n >> m >> v;
    vector <int> colors(m +1, 0);
    DSU dsu(m +1);
    for(int i = 1; i <= v; i++)
    {
        string str; cin >> str;
        int u = 0, v = 0; char eq;
        bool ok = false;
        for(char &ch : str)
        {
            if(ch == '<' || ch == '=' || ch == '>') eq = ch, ok = true;
            else
            {
                if(!ok) u = u * 10 + (ch - '0');
                else v = v * 10 + (ch - '0');
            }
        }

        if(eq == '>') swap(u, v);
        if(eq == '=') dsu.unite(u, v);
        else colors[u] = 1, colors[v] = 2;
    }

    vector <int> compos[m +1];
    for(int i = 1; i <= m; i++) compos[dsu.get(i)].emplace_back(i);

    vector <int> ans(m +1);
    for(int i = 1; i <= m; i++)
    {
        if(compos[i].size() == 0) continue;
        int color = -1;
        for(int &j : compos[i])
        {
            if(colors[j] != 0) color = colors[j];
        }

        for(int &j : compos[i]) ans[j] = color; 
    }

    for(int i = 1; i <= m; i++)
    {
        if(ans[i] == -1) cout << '?';
        else cout << 'K' << ans[i];
        cout << "\n";
    }

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

Compilation message

kovanice.cpp: In function 'void solve()':
kovanice.cpp:65:9: warning: 'eq' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         if(eq == '=') dsu.unite(u, v);
      |         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15440 KB Output is correct
2 Correct 39 ms 15452 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 22096 KB Output isn't correct
2 Halted 0 ms 0 KB -