oj.uz

Submission #680242

# Submission time Handle Problem Language Result Execution time Memory
680242 2023-01-10T10:19:54 Z raysh07 Experimental Charges (NOI19_charges) C++17
32 / 100
 32 ms 3284 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 69;
int sz[maxn];
pair<int, int> root[maxn];
 
int findroot(int x)
{
    if (x==root[x].first)
    return x;
    return root[x].first = findroot(root[x].first);
}
 
int findvalroot(int x)
{
    int s = 0;
    while (x!=root[x].first)
    {
        s+= root[x].second;
        x = root[x].first;
    }
    return s;
}
 
void unite(int x, int y, int k)
{
    x = findroot(x);
    y = findroot(y);
    if (sz[y]>sz[x])
    swap(x, y);
    sz[x]+=sz[y];
    root[y] = make_pair(x, k);
}
 
void Solve() 
{
    int n, q;
    cin>>n>>q;
    for (int i=1; i<=n; i++)
    {
        sz[i] = 1;
        root[i] = make_pair(i, 0);
    }
    for (int i=0; i<q; i++)
    {
        char ch;
        int x, y;
        cin>>ch>>x>>y;
        if (ch=='R')
        {
            if (findroot(x)==findroot(y))
            continue;
            int v1 = findvalroot(x);
            int v2 = findvalroot(y);
            
            if ((v1+v2)%2==0)
            unite(x, y, 0);
            else unite(x, y, 1);
        }
        else if (ch=='A')
        {
            if (findroot(x)==findroot(y))
            continue;
            int v1 = findvalroot(x);
            int v2 = findvalroot(y);
            
            if ((v1+v2)%2==0)
            unite(x, y, 1);
            else unite(x, y, 0);
        }
        else 
        {
            if (findroot(x)!=findroot(y))
            cout<<"?\n";
            else if (findvalroot(x)%2==findvalroot(y)%2)
            cout<<"R\n";
            else cout<<"A\n";
        }
    }
}
 
int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3100 KB Output is correct
2 Correct 21 ms 3052 KB Output is correct
3 Correct 28 ms 3028 KB Output is correct
4 Correct 22 ms 3080 KB Output is correct
5 Correct 22 ms 3148 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3272 KB Output is correct
2 Correct 23 ms 3132 KB Output is correct
3 Correct 21 ms 3172 KB Output is correct
4 Correct 30 ms 3124 KB Output is correct
5 Correct 27 ms 3284 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3156 KB Output is correct
2 Correct 32 ms 3080 KB Output is correct
3 Incorrect 25 ms 2960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 30 ms 3100 KB Output is correct
7 Correct 21 ms 3052 KB Output is correct
8 Correct 28 ms 3028 KB Output is correct
9 Correct 22 ms 3080 KB Output is correct
10 Correct 22 ms 3148 KB Output is correct
11 Correct 26 ms 3272 KB Output is correct
12 Correct 23 ms 3132 KB Output is correct
13 Correct 21 ms 3172 KB Output is correct
14 Correct 30 ms 3124 KB Output is correct
15 Correct 27 ms 3284 KB Output is correct
16 Correct 22 ms 3156 KB Output is correct
17 Correct 32 ms 3080 KB Output is correct
18 Incorrect 25 ms 2960 KB Output isn't correct
19 Halted 0 ms 0 KB -