Submission #995845

#	Time	Username	Problem	Language	Result	Execution time	Memory
995845		cpptowin	Experimental Charges (NOI19_charges)	C++17	100 / 100	36 ms	11300 KiB

charges

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
struct DSU
{
    vi par,sz,t;
    DSU(int n) : par(n),sz(n),t(n) {};
    void make(int u)
    {
        par[u] = u;
        sz[u] = 1;
        t[u] = 1e5 + 5;
    }
    int find(int u,int ti)
    {
        if(t[u] > ti) return u;
        return find(par[u],ti);
    }
    void Union(int u,int v,int ti)
    {
        u = find(u,ti);
        v = find(v,ti);
        if(u == v) return ;
        if(sz[u] < sz[v]) swap(u,v);
        sz[u] += sz[v];
        par[v] = u;
        minimize(t[v],ti);
    }
};
int n,q;
array<int,3> qry[maxn];
vii ke[maxn];
int val[maxn];
void dfs(int u,int par = 0)
{
    for(auto [v,w] : ke[u]) if(v != par and val[v] == -1)
    {
        if(w == 1) val[v] = val[u];
        else val[v] = 1 - val[u];
        dfs(v,u);
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    DSU g(n + 5);
    fo(i,1,n) g.make(i);
    fo(i,1,q)
    {
        char t;
        cin >> t >> qry[i][1] >> qry[i][2];
        if(t != 'Q') qry[i][0] = 1;
        else qry[i][0] = 2;
        if(qry[i][0] != 2)
        {
            int val = t == 'A' ? -1 : 1;
            ke[qry[i][1]].pb(qry[i][2],val);
            ke[qry[i][2]].pb(qry[i][1],val);
            g.Union(qry[i][1],qry[i][2],i);
        }
    }
    memset(val,-1,sizeof val);
    fo(i,1,n) if(val[i] == -1) val[i] = 0,dfs(i);
    fo(i,1,q) if(qry[i][0] == 2)
    {
        auto [_,u,v] = qry[i];
        if(u == v)
        {
            cout << "R";en;
            continue;
        }
        int l = 1,r = q,res = q + 1;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(g.find(u,mid) == g.find(v,mid)) res = mid,r = mid - 1;
            else l = mid + 1;
        }

        if(res > i) cout << '?';
        else
        {
            if(val[u] == val[v]) cout << 'R';
            else cout << 'A';
        }
        en;
    }
}

Compilation message (stderr)

charges.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main()
      | ^~~~
charges.cpp: In function 'int main()':
charges.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
charges.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 12 / 12
• Subtask 5: 25 / 25
• Subtask 6: 31 / 31