oj.uz

Submission #1114925

# Submission time Handle Problem Language Result Execution time Memory
1114925 2024-11-19T19:32:13 Z HoriaHaivas Inside information (BOI21_servers) C++14
50 / 100
 514 ms 46840 KB 
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct operatie
{
    char type;
    int u;
    int v;
    int moment;
    int ans;
};

struct queque
{
    int l;
    int r;
};

struct edge
{
    int to;
    int w;
};

operatie q[240005];
vector<operatie> qq[120005];
map<int,pair<int,int>> cresc;
int aib[240005];
vector<edge> nodes[120005];
bool blocked[120005];
int sz[120005];
int maxx;

void update(int idx, int delta)
{
     while (idx<=maxx)
     {
         aib[idx]+=delta;
         idx+=idx&(-idx);
     }
}

void update(int l, int r, int delta)
{
    update(l,delta);
    update(r+1,-delta);
}


int query(int idx)
{
    int ans;
    ans=0;
    while (idx>0)
    {
         ans+=aib[idx];
         idx-=idx&(-idx);
    }
    return ans;
}

int query(int l, int r)
{
    return query(r)-query(l-1);
}

void recalc(int node, int parent)
{
    sz[node]=1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            recalc(x.to,node);
            sz[node]+=sz[x.to];
        }
    }
}

int find_centroid(int node, int parent, int compsize)
{
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && sz[x.to]>compsize/2)
        {
            return find_centroid(x.to,node,compsize);
        }
    }
    return node;
}

void add_cresc(int node, int parent, int first, int last)
{
    cresc[node]= {first,last};
    update(first,last,1);
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w>last)
        {
            add_cresc(x.to,node,first,x.w);
        }
    }
}

void rem_cresc(int node, int parent, int first, int last)
{
    update(first,last,-1);
    cresc[node]= {-1,-1};
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w>last)
        {
            rem_cresc(x.to,node,first,x.w);
        }
    }
}

int globc;

void solve(int node, int parent, int first, int last)
{
    for (auto x : qq[node])
    {
        if (x.type=='Q')
        {
            if (x.u==x.v)
                q[x.moment].ans|=1;
            else if (x.u==globc && first<x.moment)
                q[x.moment].ans|=1;
            else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
                q[x.moment].ans|=0;
            else if (cresc[x.u].first>first && cresc[x.u].second<x.moment)
                q[x.moment].ans|=1;
        }
        else
        {

        }
    }
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && x.w<last)
        {
            solve(x.to,node,first,x.w);
        }
    }
}

void cd(int node)
{
    int centroid;
    cresc.clear();
    recalc(node,-1);
    centroid=find_centroid(node,-1,sz[node]);
    globc=centroid;
    blocked[centroid]=1;
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            add_cresc(x.to,centroid,x.w,x.w);
        }
    }
    for (auto x : qq[centroid])
    {
        if (x.type=='Q')
        {
            if (x.u==x.v)
                q[x.moment].ans|=1;
            else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
                q[x.moment].ans|=0;
            else if (cresc[x.u].second<x.moment)
                q[x.moment].ans|=1;
        }
        else
        {

        }
    }
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            rem_cresc(x.to,centroid,x.w,x.w);
            solve(x.to,centroid,x.w,x.w);
            add_cresc(x.to,centroid,x.w,x.w);
        }
    }
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            rem_cresc(x.to,centroid,x.w,x.w);
        }
    }
    for (auto x : nodes[centroid])
    {
        if (!blocked[x.to])
        {
            cd(x.to);
        }
    }
}

signed main()
{
    /*
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,i,j;
    cin >> n >> k;
    for (i=1; i<=n+k-1; i++)
    {
        cin >> q[i].type;
        q[i].moment=i;
        if (q[i].type=='S')
        {
            cin >> q[i].u >> q[i].v;
            nodes[q[i].u].push_back({q[i].v,i});
            nodes[q[i].v].push_back({q[i].u,i});
        }
        if (q[i].type=='Q')
        {
            cin >> q[i].u >> q[i].v;
            qq[q[i].v].push_back(q[i]);
        }
        if (q[i].type=='C')
        {
            cin >> q[i].u;
        }
    }
    maxx=n+k-1;
    cd(1);
    for (i=1; i<=n+k-1; i++)
    {
        if (q[i].type=='Q')
        {
            if (q[i].ans==1)
                cout << "yes\n";
            else
                cout << "no\n";
        }
        else
        {
            //cout << q[i].ans << "\n";
        }
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:224:15: warning: unused variable 'j' [-Wunused-variable]
  224 |     int n,k,i,j;
      |               ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23012 KB Output is correct
2 Correct 34 ms 24672 KB Output is correct
3 Correct 40 ms 23368 KB Output is correct
4 Correct 34 ms 24648 KB Output is correct
5 Correct 33 ms 24648 KB Output is correct
6 Correct 64 ms 24248 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23012 KB Output is correct
2 Correct 34 ms 24672 KB Output is correct
3 Correct 40 ms 23368 KB Output is correct
4 Correct 34 ms 24648 KB Output is correct
5 Correct 33 ms 24648 KB Output is correct
6 Correct 64 ms 24248 KB Output is correct
7 Incorrect 25 ms 22576 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 23 ms 23012 KB Output is correct
2 Correct 262 ms 40988 KB Output is correct
3 Correct 276 ms 41020 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23012 KB Output is correct
2 Correct 262 ms 40988 KB Output is correct
3 Correct 276 ms 41020 KB Output is correct
4 Incorrect 28 ms 22552 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 22 ms 22920 KB Output is correct
2 Correct 206 ms 37708 KB Output is correct
3 Correct 203 ms 37784 KB Output is correct
4 Correct 507 ms 46840 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22920 KB Output is correct
2 Correct 206 ms 37708 KB Output is correct
3 Correct 203 ms 37784 KB Output is correct
4 Correct 507 ms 46840 KB Output is correct
5 Incorrect 22 ms 22568 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 25 ms 23020 KB Output is correct
2 Correct 450 ms 37808 KB Output is correct
3 Correct 196 ms 35144 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23020 KB Output is correct
2 Correct 450 ms 37808 KB Output is correct
3 Correct 196 ms 35144 KB Output is correct
4 Incorrect 22 ms 22576 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 21 ms 23020 KB Output is correct
2 Correct 187 ms 37704 KB Output is correct
3 Correct 234 ms 37832 KB Output is correct
4 Correct 460 ms 46664 KB Output is correct
5 Correct 22 ms 23020 KB Output is correct
6 Correct 388 ms 37960 KB Output is correct
7 Correct 182 ms 35144 KB Output is correct
8 Correct 203 ms 35400 KB Output is correct
9 Correct 200 ms 35656 KB Output is correct
10 Correct 440 ms 42200 KB Output is correct
11 Correct 430 ms 42056 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23020 KB Output is correct
2 Correct 187 ms 37704 KB Output is correct
3 Correct 234 ms 37832 KB Output is correct
4 Correct 460 ms 46664 KB Output is correct
5 Correct 22 ms 23020 KB Output is correct
6 Correct 388 ms 37960 KB Output is correct
7 Correct 182 ms 35144 KB Output is correct
8 Correct 203 ms 35400 KB Output is correct
9 Correct 200 ms 35656 KB Output is correct
10 Correct 440 ms 42200 KB Output is correct
11 Correct 430 ms 42056 KB Output is correct
12 Incorrect 20 ms 22576 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 21 ms 23020 KB Output is correct
2 Correct 42 ms 24808 KB Output is correct
3 Correct 40 ms 23368 KB Output is correct
4 Correct 35 ms 24648 KB Output is correct
5 Correct 31 ms 24652 KB Output is correct
6 Correct 57 ms 24348 KB Output is correct
7 Correct 23 ms 23020 KB Output is correct
8 Correct 256 ms 41040 KB Output is correct
9 Correct 240 ms 40832 KB Output is correct
10 Correct 21 ms 23012 KB Output is correct
11 Correct 195 ms 37672 KB Output is correct
12 Correct 207 ms 37708 KB Output is correct
13 Correct 514 ms 46664 KB Output is correct
14 Correct 21 ms 23020 KB Output is correct
15 Correct 434 ms 37848 KB Output is correct
16 Correct 213 ms 35144 KB Output is correct
17 Correct 200 ms 35552 KB Output is correct
18 Correct 203 ms 35656 KB Output is correct
19 Correct 403 ms 42124 KB Output is correct
20 Correct 466 ms 42056 KB Output is correct
21 Correct 316 ms 39984 KB Output is correct
22 Correct 331 ms 37796 KB Output is correct
23 Correct 221 ms 34788 KB Output is correct
24 Correct 232 ms 35068 KB Output is correct
25 Correct 299 ms 39356 KB Output is correct
26 Correct 202 ms 34888 KB Output is correct
27 Correct 176 ms 35700 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23020 KB Output is correct
2 Correct 42 ms 24808 KB Output is correct
3 Correct 40 ms 23368 KB Output is correct
4 Correct 35 ms 24648 KB Output is correct
5 Correct 31 ms 24652 KB Output is correct
6 Correct 57 ms 24348 KB Output is correct
7 Correct 23 ms 23020 KB Output is correct
8 Correct 256 ms 41040 KB Output is correct
9 Correct 240 ms 40832 KB Output is correct
10 Correct 21 ms 23012 KB Output is correct
11 Correct 195 ms 37672 KB Output is correct
12 Correct 207 ms 37708 KB Output is correct
13 Correct 514 ms 46664 KB Output is correct
14 Correct 21 ms 23020 KB Output is correct
15 Correct 434 ms 37848 KB Output is correct
16 Correct 213 ms 35144 KB Output is correct
17 Correct 200 ms 35552 KB Output is correct
18 Correct 203 ms 35656 KB Output is correct
19 Correct 403 ms 42124 KB Output is correct
20 Correct 466 ms 42056 KB Output is correct
21 Correct 316 ms 39984 KB Output is correct
22 Correct 331 ms 37796 KB Output is correct
23 Correct 221 ms 34788 KB Output is correct
24 Correct 232 ms 35068 KB Output is correct
25 Correct 299 ms 39356 KB Output is correct
26 Correct 202 ms 34888 KB Output is correct
27 Correct 176 ms 35700 KB Output is correct
28 Incorrect 24 ms 22576 KB Extra information in the output file
29 Halted 0 ms 0 KB -