제출 #899748

#제출 시각아이디문제언어결과실행 시간메모리
899748PekibanKOVANICE (COI15_kovanice)C++17
100 / 100
160 ms54708 KiB
#include <bits/stdc++.h> using namespace std; array<int, 3> f(string s) { int i = 0, x = 0; array<int, 3> a; while (s[i] != '<' && s[i] != '>' && s[i] != '=') { x*=10; x += (s[i] - '0'); i++; } a[0] = x, a[1] = (s[i] == '<' ? 0 : (s[i] == '>' ? 1 : 2)); x = 0, i++; while (i < s.size()) { x*=10; x += (s[i] - '0'); i++; } a[2] = x; return a; } const int mxN = 3e5+2; int p[mxN], sz[mxN], mx[mxN], ans[mxN]; bool visited[mxN]; vector<int> g[mxN], mxv[mxN], dir[mxN], ord; int findset(int s) { if (s == p[s]) return s; return p[s] = findset(p[s]); } void unite(int u, int v) { u = findset(u), v = findset(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); p[v] = u; sz[u] += sz[v]; } void dfs(int s) { visited[s] = 1; for (auto u : g[s]) { if (visited[u]) continue; dfs(u); } ord.push_back(s); } void dfspush(int s, int x) { visited[s] = 1; ans[s] = x; for (auto u : mxv[s]) { if (visited[u]) continue; dfspush(u, x-1); } } int main() { ios::sync_with_stdio(0); cin.tie(0); iota(p, p+mxN, 0); fill(sz, sz+mxN, 1); int n, m, v; cin >> n >> m >> v; for (int i = 0; i < v; ++i) { string s; cin >> s; auto [x, r, y] = f(s); if (r == 2) { unite(x, y); } else if (r == 1) { dir[x].push_back(y); } else { dir[y].push_back(x); } } for (int i = 1; i <= m; ++i) { for (auto u : dir[i]) { g[findset(i)].push_back(findset(u)); } } for (int i = 1; i <= m; ++i) { if (!visited[findset(i)]) { dfs(findset(i)); } } for (auto i : ord) { for (auto u : g[i]) { mx[i] = max(mx[i], mx[u]+1); } for (auto u : g[i]) { if (mx[u]+1 == mx[i]) { mxv[i].push_back(u); } } } fill(visited, visited+mxN, 0); for (auto i : ord) { if (mx[i] == n-1) { dfspush(i, n); } } for (int i = 1; i <= m; ++i) { if (ans[findset(i)]) { cout << "K" << ans[findset(i)] << '\n'; } else { cout << "?" << '\n'; } } }

컴파일 시 표준 에러 (stderr) 메시지

kovanice.cpp: In function 'std::array<int, 3> f(std::string)':
kovanice.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (i < s.size()) {
      |            ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...