# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
585727 | red24 | Experimental Charges (NOI19_charges) | C++14 | 144 ms | 9144 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int>
#define ppi pair<pair<int>>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define OK cout << "OK" << '\n'
#define qi queue<int>
#define sti stack<int>
#define si stack<int>
#define yes cout << "Yes" << '\n'
#define no cout << "No" << '\n'
#define pb push_back
#define eb emplace_back
#define vpi vector<pair<int, int>>
#define ll long long
#define nl cout << '\n'
#define ok cout << "OK" << '\n'
void printvec(vi v)
{
rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
}
// PROGRAM
const int MOD = (int)1e9 + 7;
const int mx = 2e5;
int par[mx];
int siz[mx];
bool col[mx];
vi chds[mx];
void make_set(int x)
{
par[x] = x;
siz[x] = 1;
col[x] = 1;
chds[x].pb(x);
}
int find_set(int x)
{
if (par[x] == x) return x;
else return par[x] = find_set(par[x]);
}
void update(int x, int y)
{
int px = find_set(x);
for (auto k : chds[y])
{
col[k] = !col[k];
chds[px].pb(k);
}
chds[y].clear();
}
void unite(int x, int y, bool charge)
{
bool ox = col[x];
bool oy = col[y];
x = find_set(x); y = find_set(y);
if (x == y) return;
if (siz[x] < siz[y]) swap(x, y);
if ((charge == 1 && ox == oy) || (charge == 0 && ox != oy)) update(x, y);
siz[x] += siz[y];
par[y] = x;
}
void solve()
{
// CHECK IF PROGRAM HAS TESTCASES
int n, q; cin >> n >> q;
rep(i, 1, n) make_set(i);
while (q--)
{
char t; cin >> t;
int a, b; cin >> a >> b;
// PART ONE
if (t == 'A')
{
unite(a, b, 1);
}
else if (t == 'R')
{
unite(a, b, 0);
}
else
{
if (find_set(a) != find_set(b)) cout << "?" << '\n';
else if (col[a] == col[b]) cout << "R" << '\n';
else cout << "A" << '\n';
}
}
}
int main()
{
int T = 1;
// cin >> T;
while (T--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |