oj.uz

답안 #679502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679502 2023-01-08T12:26:05 Z stevancv KOVANICE (COI15_kovanice) C++14
100 / 100
 274 ms 37488 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(a, b)
using namespace std;
const int N = 3e5 + 2;
const int mod = 1e9 + 7;
int Convert(string s, int l, int r) {
    int ans = 0;
    for (int i = l; i <= r; i++) {
        ans = 10 * ans + (s[i] - '0');
    }
    return ans;
}
int link[N], mx[2][N];
bool was[2][N];
vector<int> g[2][N];
int Find(int u) {
    if (u == link[u]) return u;
    return link[u] = Find(link[u]);
}
void Unite(int u, int v) {
    u = Find(u);
    v = Find(v);
    link[v] = u;
}
void Dfs(int s, int y) {
    if (was[y][s]) return;
    was[y][s] = 1;
    for (int u : g[y][s]) {
        Dfs(u, y);
        smax(mx[y][s], mx[y][u] + 1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, v;
    cin >> n >> m >> v;
    for (int i = 1; i <= m; i++) link[i] = i;
    vector<array<int, 2>> e;
    for (int i = 0; i < v; i++) {
        string s; cin >> s;
        int pos = -1;
        for (int j = 0; j < s.size(); j++) {
            if (!('0' <= s[j] && s[j] <= '9')) pos = j;
        }
        int x = Convert(s, 0, pos - 1);
        int y = Convert(s, pos + 1, s.size() - 1);
        if (s[pos] == '=') Unite(x, y);
        if (s[pos] == '<') e.push_back({x, y});
        if (s[pos] == '>') e.push_back({y, x});
    }
    for (int i = 0; i < e.size(); i++) {
        int x = Find(e[i][0]); int y = Find(e[i][1]);
        g[0][x].push_back(y);
        g[1][y].push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        int j = Find(i);
        if (!was[0][j]) Dfs(j, 0);
        if (!was[1][j]) Dfs(j, 1);
    }
    for (int i = 1; i <= m; i++) {
        int j = Find(i);
        if (mx[0][j] + mx[1][j] == n - 1) cout << 'K' << mx[1][j] + 1 << en;
        else cout << '?' << en;
    }
    return 0;
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int j = 0; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~
kovanice.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < e.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14504 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 20584 KB Output is correct
2 Correct 68 ms 22028 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 16336 KB Output is correct
2 Correct 22 ms 17100 KB Output is correct
3 Correct 25 ms 17144 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 28956 KB Output is correct
2 Correct 195 ms 32000 KB Output is correct
3 Correct 191 ms 31860 KB Output is correct
4 Correct 270 ms 36700 KB Output is correct
5 Correct 274 ms 37488 KB Output is correct