oj.uz

Submission #846132

# Submission time Handle Problem Language Result Execution time Memory
846132 2023-09-07T11:25:49 Z vjudge1 KOVANICE (COI15_kovanice) C++17
60 / 100
 141 ms 71604 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;


struct Dsu {
  vector<int> s, p;
  int sz;
  Dsu(int n){
    sz = n;
    s.resize(n+1, 1);
    p.resize(n+1);
    for(int i = 0; i <= n; ++i) p[i] = i;
  }
  int find(int v){
    if(p[v] == v) return v;
    return (p[v] = find(p[v]));
  }
  void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
      if(s[a] > s[b]){
        swap(a, b);
      }
      s[b] += s[a];
      p[a] = b;
      sz--;
    }
  }
};


int n, m, k;
vector<int> g[N], r[N], in(N), dep(N), out(N);
vector<bool> vis(N), ok(N);
void solve(){
  cin >> n >> m >> k;
  Dsu d(m);
  vector<pair<int, int>> edges;
  for(int i = 0; i < k; ++i){
    string s; cin >> s;
    int num1 = 0, num2 = 0;
    bool flag = 0, tp;
    for(char c: s){
      if(c == '=' || c == '<'){
        flag = 1;
        tp = (c == '=');
        continue;
      }
      if(flag){
        num2 = num2*10 + (c-'0');
      }else{
        num1 = num1*10 + (c-'0');
      }
    }
    if(tp) d.merge(num1, num2);
    else{
      edges.pb({num1, num2});
    }
  }
  for(auto e: edges){
    g[d.find(e.second)].pb(d.find(e.first));
    r[d.find(e.first)].pb(d.find(e.second));
    in[d.find(e.first)]++, out[d.find(e.second)]++;
  }
  queue<int> q;
  for(int i = 1; i <= m; ++i){
    if(d.find(i) == i && in[i] == 0){
      q.push(i);
    }
  }
  while(!q.empty()){
    int v = q.front(); q.pop();
    if(dep[v] == n - 1){
      ok[v] = 1;
    }
    for(int u: g[v]){
      in[u]--;
      dep[u] = max(dep[u], dep[v] + 1);
      if(in[u] == 0){
        q.push(u);
      }
    }
  }
  for(int i = 1; i <= m; ++i){
    if(d.find(i) == i && out[i] == 0 && ok[i]){
      q.push(i);
    }
  }
  while(!q.empty()){
    int v = q.front(); q.pop();
    for(int u: r[v]){
      out[u]--;
      if(dep[u] == dep[v] - 1) ok[u] = 1;
      if(out[u] == 0){
        if(ok[u])
          q.push(u);
      }
    }
  }
  for(int i = 1; i <= m; ++i){
    if(ok[d.find(i)]){
      cout << "K" << n-dep[d.find(i)] << '\n';
    }else{
      cout << "?\n";
    }
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:121:15: warning: unused variable 'aa' [-Wunused-variable]
  121 |   int tt = 1, aa;
      |               ^~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:64:5: warning: 'tp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     if(tp) d.merge(num1, num2);
      |     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 59484 KB Output is correct
2 Correct 16 ms 59484 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 64976 KB Output is correct
2 Correct 60 ms 65564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61140 KB Output is correct
2 Correct 24 ms 61144 KB Output is correct
3 Correct 24 ms 61144 KB Output is correct

Subtask #4
0 / 40.0

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