oj.uz

Submission #623974

# Submission time Handle Problem Language Result Execution time Memory
623974 2022-08-07T06:06:30 Z tamthegod KOVANICE (COI15_kovanice) C++14
100 / 100
 230 ms 96880 KB 
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, m, k;
string s[maxN];
int lab[maxN];
int node[maxN];
vector<int> adj[maxN];
int res[maxN], res1[maxN];
int Findset(int u)
{
    return lab[u] < 0 ? u : lab[u] = Findset(lab[u]);
}
void Unite(int u, int v)
{
    int r = Findset(u), s = Findset(v);
    if(r == s) return;
    if(lab[r] > lab[s]) swap(r, s);
    lab[r] += lab[s];
    lab[s] = r;
}
void ReadInput()
{
    cin >> n >> m >> k;
    for(int i=1; i<=k; i++) cin >> s[i];
}
deque<int> L;
int depth[maxN];
int vis[maxN];
void dfs(int u)
{
    vis[u] = -1;
    for(int v : adj[u])
        if(!vis[v]) dfs(v);
    L.push_front(u);
}
int to_num(string s)
{
    int res = 0;
    for(char c : s)
        res = res * 10 + c - '0';
    return res;
}
void Solve()
{
    memset(lab, -1, sizeof lab);
    memset(res, 3, sizeof res);
    for(int i=1; i<=k; i++)
    {
        int j = 0;
        while(s[i][j] >= '0' && s[i][j] <= '9') j++;
        if(s[i][j] == '=')
        {
            int u = to_num(s[i].substr(0, j)), v = to_num(s[i].substr(j + 1, s[i].size() - j + 1));
          //  cout << u << " " << v << " " << s[i] << '\n';
            Unite(u, v);
        }
    }
    int p = 0;
    for(int i=1; i<=m; i++)
    {
        if(!node[Findset(i)]) node[Findset(i)] = ++p;
        node[i] = node[Findset(i)];
    }
    for(int i=1; i<=k; i++)
    {
        int j = 0;
        while(s[i][j] >= '0' && s[i][j] <= '9') j++;
        int u = to_num(s[i].substr(0, j)), v = to_num(s[i].substr(j + 1, s[i].size() - j + 1));
        u = node[u], v = node[v];
        if(s[i][j] == '<') adj[u].pb(v);
        if(s[i][j] == '>') adj[v].pb(u);
    }
    for(int i=1; i<=p; i++)
        if(!vis[i]) dfs(i);
  //  for(int v : L) cout << v << " ";return;
    memset(vis, 0, sizeof vis);
    for(int v : L)
    {
        depth[v] = max(1ll, depth[v]);
        for(int x : adj[v])
            depth[x] = max(depth[x], depth[v] + 1);
    }
    //cout << depth[2];return;
    reverse(L.begin(), L.end());
    for(int v : L)
    {
        //assert(depth[v] <= n);
        if(depth[v] == n)
        {
            res[v] = n;
            continue;
        }
        for(int x : adj[v])
            if(res[x]) res[v] = min(res[v], res[x] - 1);
    }
    //for(int i=1; i<=p; i++) cout << res[i] << '\n';return;
   // cout << node[5];return;
    for(int i=1; i<=m; i++)
    {
        if(res[node[i]] > n || res[node[i]] != depth[node[i]]) cout << "?" << '\n';
        else cout << 'K' << res[node[i]] << '\n';
    }
}
int32_t main()
{
 //   freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78540 KB Output is correct
2 Correct 35 ms 78564 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 84504 KB Output is correct
2 Correct 90 ms 84696 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 79692 KB Output is correct
2 Correct 46 ms 79776 KB Output is correct
3 Correct 55 ms 79784 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 89824 KB Output is correct
2 Correct 170 ms 92916 KB Output is correct
3 Correct 178 ms 92920 KB Output is correct
4 Correct 209 ms 96192 KB Output is correct
5 Correct 230 ms 96880 KB Output is correct