oj.uz

Submission #1120511

# Submission time Handle Problem Language Result Execution time Memory
1120511 2024-11-28T08:00:29 Z vjudge1 KOVANICE (COI15_kovanice) C++17
0 / 100
 78 ms 15416 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define FORI(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, n) for(ll i = 1; i <= n; i++)
typedef vector<ll> vl; 
typedef set<ll> setl;
#define ff first
#define ss second    
#define all(v) v.begin(), v.end() 
#define pll pair<ll, ll> 
#define db double
#define nll cout << "\n"
#define nl "\n"
#define sync ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const ll mod =  1e9 + 7;
const int MAX = 300000 + 5;
const ll lmax = 9223372036854775807;
const int imax = 2147483647;
ll n, m, k, res, rnk[MAX];
// ll a[MAX];
class dsu {
  int n;
  vector <int> root, sz;
  int comp;
  public :
    dsu(int _n) : n(_n) {
      root.resize(n);
      sz.resize(n, 1);
      iota(root.begin(), root.end(), (int)0);
      comp = n;
    }
    
    int get_root(int u) {
      return (u == root[u]? u: (root[u] = get_root(root[u])));
    }
    
    bool connected(int u, int v) {
      if (get_root(u) == get_root(v))
        return true;
      return false;
    }
    
    void merge(int u, int v) {
      if (connected(u, v))
        return ;
      u = get_root(u);
      v = get_root(v);
      comp--;
      if (sz[v] > sz[u])
        swap(u, v);
      root[v] = u;
      sz[u] += sz[v];
    }
    
    int components() {
      return comp;
    }
};
void solve(){
    cin >> n >> m >> k;
    string s;
    vector < pair < ll, pll > > v;
    ll a, b;
    dsu t(m + 1);
    FOR(i, k){
        cin >> s;
        a = (s[0] - '0');
        b = (s[2] - '0');
        if(s[1] == '='){
            if(a > b)swap(a, b);
            t.merge(a, b);
        }
        else if(s[1] == '>'){
            v.push_back({2, {a, b}});
        }
        else{
            v.push_back({1, {a, b}});
        }
    }
    sort(all(v));
    FORI(i, k){
        if(v[i].ff){
            a = v[i].ss.ff;
            b = v[i].ss.ss;
            if(v[i].ff == 1){
                rnk[t.get_root(a)] = 1;
                rnk[t.get_root(b)] = 2;
            }
            else if(v[i].ff == 2){
                rnk[t.get_root(b)] = 1;
                rnk[t.get_root(a)] = 2;
            }
        }
    }
    FOR(i, m){
        if(rnk[t.get_root(i)] == 0){
            cout << '?';
        }
        else {
            if(rnk[t.get_root(i)] == 1)cout << "K1";
            else cout << "K2";
        }
        nll;
    }
}
signed main(){  
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    sync;
    ll t = 1;
    // cin >> t;
    FOR(i, t){
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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