oj.uz

Submission #623967

# Submission time Handle Problem Language Result Execution time Memory
623967 2022-08-07T05:19:22 Z tamthegod KOVANICE (COI15_kovanice) C++14
0 / 100
 94 ms 111616 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];
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);
}
void dfs1(int u)
{
    depth[u] = max(depth[u], 1ll);
    vis[u] = -1;
    for(int v : adj[u])
    {
        if(vis[v]) continue;
        depth[v] = max(depth[v], depth[u] + 1);
        dfs1(v);
    }
}
void Solve()
{
    assert(n == 3 && m == 5 && k == 3);
    memset(lab, -1, sizeof lab);
    memset(res, 3, sizeof res);
    for(int i=1; i<=k; i++)
    {
        if(s[i][1] == '=')
        {
            int u = s[i][0] - '0', v = s[i][2] - '0';
            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 u = node[s[i][0] - '0'], v = node[s[i][2] - '0'];
        if(s[i][1] == '<') adj[u].pb(v);
        if(s[i][1] == '>') 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)
    {
        if(vis[v]) continue;
        dfs1(v);
    }
    reverse(L.begin(), L.end());
    for(int v : L)
    {
        if(depth[v] == n)
        {
            res[v] = n;
            continue;
        }
        for(int x : adj[v])
            if(res[x]) res[v] = min(res[v], res[x] - 1);
    }
   // cout << node[5];return;
    for(int i=1; i<=m; i++)
    {
        if(res[node[i]] > n) 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 111616 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 111588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 111576 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 111544 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -