oj.uz

Submission #718242

# Submission time Handle Problem Language Result Execution time Memory
718242 2023-04-03T17:40:52 Z n0sk1ll Inside information (BOI21_servers) C++14
50 / 100
 359 ms 129228 KB 
#include <bits/stdc++.h>
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
 
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
 
 
 
 
 
 
 
//Note to self: Check for overflow
 
int n;
 
int idx=0;
bool val[44000007];
int L[44000007],R[44000007];
 
void add(int p, int q, int l, int r, int x)
{
    if (l==x && x==r) val[p]=1;
    else if (l<=x && x<=r)
    {
        val[p]=1; int mid=(l+r)/2;
        if (x<=mid) R[p]=R[q],L[p]=++idx,add(L[p],L[q],l,mid,x);
        else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,x);
    }
}
 
bool qry(int p, int l, int r, int s)
{
    if (l==r) return val[p];
    int mid=(l+r)/2;
    if (s<=mid) return qry(L[p],l,mid,s);
    else return qry(R[p],mid+1,r,s);
}
 
vector<int> svi;
void dfs(int p, int l, int r)
{
    if (!val[p]) return;
    if (l==r) svi.pb(l);
    else
    {
        int mid=(l+r)/2;
        dfs(L[p],l,mid);
        dfs(R[p],mid+1,r);
    }
}
 
int root[125005];
int siz[125005];
 
void spoji(int a, int b)
{
    if (siz[a]>siz[b]) swap(a,b);
    dfs(root[a],1,n); int tmp;
    for (auto it : svi) tmp=++idx,add(tmp,root[b],1,n,it),root[b]=tmp;
    root[a]=tmp,root[b]=tmp,siz[b]+=siz[a],siz[a]=siz[b];
    svi.clear();
}
 
int main()
{
    FAST;
 
    int q; cin>>n>>q;
    fff(i,1,n) root[i]=++idx,siz[i]=1;
    fff(i,1,n)
    {
        int tmp=++idx;
        add(tmp,root[i],1,n,i);
        root[i]=tmp;
    }
 
    q+=n-1;
    while (q--)
    {
        char t; cin>>t;
        if (t=='C') return cout<<"necu radim",0;
        if (t=='S')
        {
            int u,v; cin>>u>>v;
            spoji(u,v);
        }
        else //t=='Q'
        {
            int u,x; cin>>u>>x;
            cout<<(qry(root[u],1,n,x)?"yes":"no")<<"\n";
        }
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:13:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
servers.cpp:92:5: note: in expansion of macro 'fff'
   92 |     fff(i,1,n) root[i]=++idx,siz[i]=1;
      |     ^~~
servers.cpp:13:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
servers.cpp:93:5: note: in expansion of macro 'fff'
   93 |     fff(i,1,n)
      |     ^~~
servers.cpp: In function 'void spoji(int, int)':
servers.cpp:83:12: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |     root[a]=tmp,root[b]=tmp,siz[b]+=siz[a],siz[a]=siz[b];
      |     ~~~~~~~^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1716 KB Output is correct
2 Correct 38 ms 3260 KB Output is correct
3 Correct 36 ms 3416 KB Output is correct
4 Correct 39 ms 3192 KB Output is correct
5 Correct 46 ms 3164 KB Output is correct
6 Correct 37 ms 2976 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1716 KB Output is correct
2 Correct 38 ms 3260 KB Output is correct
3 Correct 36 ms 3416 KB Output is correct
4 Correct 39 ms 3192 KB Output is correct
5 Correct 46 ms 3164 KB Output is correct
6 Correct 37 ms 2976 KB Output is correct
7 Incorrect 2 ms 472 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1612 KB Output is correct
2 Correct 312 ms 42316 KB Output is correct
3 Correct 275 ms 42300 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1612 KB Output is correct
2 Correct 312 ms 42316 KB Output is correct
3 Correct 275 ms 42300 KB Output is correct
4 Incorrect 1 ms 468 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1528 KB Output is correct
2 Correct 221 ms 50232 KB Output is correct
3 Correct 203 ms 50188 KB Output is correct
4 Correct 185 ms 43056 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1528 KB Output is correct
2 Correct 221 ms 50232 KB Output is correct
3 Correct 203 ms 50188 KB Output is correct
4 Correct 185 ms 43056 KB Output is correct
5 Incorrect 1 ms 468 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1548 KB Output is correct
2 Correct 207 ms 110164 KB Output is correct
3 Correct 268 ms 52172 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1548 KB Output is correct
2 Correct 207 ms 110164 KB Output is correct
3 Correct 268 ms 52172 KB Output is correct
4 Incorrect 1 ms 468 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1532 KB Output is correct
2 Correct 218 ms 50152 KB Output is correct
3 Correct 211 ms 50136 KB Output is correct
4 Correct 128 ms 43032 KB Output is correct
5 Correct 31 ms 1592 KB Output is correct
6 Correct 249 ms 110148 KB Output is correct
7 Correct 240 ms 52216 KB Output is correct
8 Correct 243 ms 52700 KB Output is correct
9 Correct 265 ms 52680 KB Output is correct
10 Correct 296 ms 59912 KB Output is correct
11 Correct 308 ms 61096 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1532 KB Output is correct
2 Correct 218 ms 50152 KB Output is correct
3 Correct 211 ms 50136 KB Output is correct
4 Correct 128 ms 43032 KB Output is correct
5 Correct 31 ms 1592 KB Output is correct
6 Correct 249 ms 110148 KB Output is correct
7 Correct 240 ms 52216 KB Output is correct
8 Correct 243 ms 52700 KB Output is correct
9 Correct 265 ms 52680 KB Output is correct
10 Correct 296 ms 59912 KB Output is correct
11 Correct 308 ms 61096 KB Output is correct
12 Incorrect 1 ms 468 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1612 KB Output is correct
2 Correct 37 ms 3272 KB Output is correct
3 Correct 41 ms 3336 KB Output is correct
4 Correct 38 ms 3128 KB Output is correct
5 Correct 37 ms 3128 KB Output is correct
6 Correct 41 ms 3052 KB Output is correct
7 Correct 27 ms 1588 KB Output is correct
8 Correct 256 ms 42340 KB Output is correct
9 Correct 272 ms 42296 KB Output is correct
10 Correct 26 ms 1488 KB Output is correct
11 Correct 197 ms 50128 KB Output is correct
12 Correct 192 ms 50296 KB Output is correct
13 Correct 149 ms 43064 KB Output is correct
14 Correct 31 ms 1492 KB Output is correct
15 Correct 256 ms 110220 KB Output is correct
16 Correct 244 ms 52192 KB Output is correct
17 Correct 221 ms 52768 KB Output is correct
18 Correct 259 ms 52744 KB Output is correct
19 Correct 282 ms 59824 KB Output is correct
20 Correct 281 ms 61188 KB Output is correct
21 Correct 244 ms 46152 KB Output is correct
22 Correct 303 ms 52052 KB Output is correct
23 Correct 274 ms 54484 KB Output is correct
24 Correct 248 ms 54520 KB Output is correct
25 Correct 247 ms 46508 KB Output is correct
26 Correct 359 ms 121612 KB Output is correct
27 Correct 350 ms 129228 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1612 KB Output is correct
2 Correct 37 ms 3272 KB Output is correct
3 Correct 41 ms 3336 KB Output is correct
4 Correct 38 ms 3128 KB Output is correct
5 Correct 37 ms 3128 KB Output is correct
6 Correct 41 ms 3052 KB Output is correct
7 Correct 27 ms 1588 KB Output is correct
8 Correct 256 ms 42340 KB Output is correct
9 Correct 272 ms 42296 KB Output is correct
10 Correct 26 ms 1488 KB Output is correct
11 Correct 197 ms 50128 KB Output is correct
12 Correct 192 ms 50296 KB Output is correct
13 Correct 149 ms 43064 KB Output is correct
14 Correct 31 ms 1492 KB Output is correct
15 Correct 256 ms 110220 KB Output is correct
16 Correct 244 ms 52192 KB Output is correct
17 Correct 221 ms 52768 KB Output is correct
18 Correct 259 ms 52744 KB Output is correct
19 Correct 282 ms 59824 KB Output is correct
20 Correct 281 ms 61188 KB Output is correct
21 Correct 244 ms 46152 KB Output is correct
22 Correct 303 ms 52052 KB Output is correct
23 Correct 274 ms 54484 KB Output is correct
24 Correct 248 ms 54520 KB Output is correct
25 Correct 247 ms 46508 KB Output is correct
26 Correct 359 ms 121612 KB Output is correct
27 Correct 350 ms 129228 KB Output is correct
28 Incorrect 1 ms 468 KB Extra information in the output file
29 Halted 0 ms 0 KB -