Submission #1120723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120723		Fikrat_Asadzadeh	KOVANICE (COI15_kovanice)	C++14	10 / 100	49 ms	12680 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#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(MAX + 1);
    FOR(i, k){
        cin >> s;
        ll ind;
        a = 0;
        b = 0;
        FORI(i, s.size()){
            if(!isdigit(s[i])){
                ind = i;
                break;
            }
            a = a * 10 + (s[i] - '0');
        }
        for(ll i = ind + 1; i < s.size(); i++)b = b * 10 + (s[i] - '0');
        if(s[ind] == '='){
            t.merge(a, b);
        }
        else if(s[ind] == '>'){
            v.push_back({2, {a, b}});
        }
        else{
            v.push_back({1, {a, b}});
        }
    }
    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();
    }
}

Compilation message (stderr)

kovanice.cpp:20:17: warning: overflow in conversion from 'long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   20 | const ll lmax = 9223372036854775807;
      |                 ^~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FORI(i, n) for(ll i = 0; i < n; i++)
......
   73 |         FORI(i, s.size()){
      |              ~~~~~~~~~~~            
kovanice.cpp:73:9: note: in expansion of macro 'FORI'
   73 |         FORI(i, s.size()){
      |         ^~~~
kovanice.cpp:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(ll i = ind + 1; i < s.size(); i++)b = b * 10 + (s[i] - '0');
      |                             ~~^~~~~~~~~~
kovanice.cpp:80:16: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |         for(ll i = ind + 1; i < s.size(); i++)b = b * 10 + (s[i] - '0');
      |                ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40