oj.uz

Submission #1114425

# Submission time Handle Problem Language Result Execution time Memory
1114425 2024-11-18T20:35:51 Z HoriaHaivas Inside information (BOI21_servers) C++14
50 / 100
 365 ms 45896 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 edge
{
    int to;
    int w;
};

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

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};
    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)
{
    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.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;
    }
    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 last)
{
    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.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;
    }
    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])
        {
            cd(x.to,centroid);
        }
    }
}

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;
        }
    }
    cd(1,0);
    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";
        }
    }
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19948 KB Output is correct
2 Correct 35 ms 22356 KB Output is correct
3 Correct 41 ms 21292 KB Output is correct
4 Correct 34 ms 22512 KB Output is correct
5 Correct 37 ms 22600 KB Output is correct
6 Correct 63 ms 22344 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19948 KB Output is correct
2 Correct 35 ms 22356 KB Output is correct
3 Correct 41 ms 21292 KB Output is correct
4 Correct 34 ms 22512 KB Output is correct
5 Correct 37 ms 22600 KB Output is correct
6 Correct 63 ms 22344 KB Output is correct
7 Incorrect 24 ms 20624 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 22 ms 19940 KB Output is correct
2 Correct 236 ms 36304 KB Output is correct
3 Correct 273 ms 36268 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19940 KB Output is correct
2 Correct 236 ms 36304 KB Output is correct
3 Correct 273 ms 36268 KB Output is correct
4 Incorrect 30 ms 19752 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 26 ms 20088 KB Output is correct
2 Correct 190 ms 35920 KB Output is correct
3 Correct 188 ms 35852 KB Output is correct
4 Correct 350 ms 45896 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 20088 KB Output is correct
2 Correct 190 ms 35920 KB Output is correct
3 Correct 188 ms 35852 KB Output is correct
4 Correct 350 ms 45896 KB Output is correct
5 Incorrect 26 ms 20528 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 23 ms 19980 KB Output is correct
2 Correct 278 ms 36008 KB Output is correct
3 Correct 136 ms 33240 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19980 KB Output is correct
2 Correct 278 ms 36008 KB Output is correct
3 Correct 136 ms 33240 KB Output is correct
4 Incorrect 22 ms 20528 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 20088 KB Output is correct
2 Correct 194 ms 35864 KB Output is correct
3 Correct 217 ms 35912 KB Output is correct
4 Correct 314 ms 45768 KB Output is correct
5 Correct 21 ms 20972 KB Output is correct
6 Correct 266 ms 36168 KB Output is correct
7 Correct 138 ms 33144 KB Output is correct
8 Correct 143 ms 33376 KB Output is correct
9 Correct 138 ms 33864 KB Output is correct
10 Correct 299 ms 40776 KB Output is correct
11 Correct 320 ms 40520 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20088 KB Output is correct
2 Correct 194 ms 35864 KB Output is correct
3 Correct 217 ms 35912 KB Output is correct
4 Correct 314 ms 45768 KB Output is correct
5 Correct 21 ms 20972 KB Output is correct
6 Correct 266 ms 36168 KB Output is correct
7 Correct 138 ms 33144 KB Output is correct
8 Correct 143 ms 33376 KB Output is correct
9 Correct 138 ms 33864 KB Output is correct
10 Correct 299 ms 40776 KB Output is correct
11 Correct 320 ms 40520 KB Output is correct
12 Incorrect 20 ms 20596 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 19940 KB Output is correct
2 Correct 36 ms 22352 KB Output is correct
3 Correct 43 ms 21320 KB Output is correct
4 Correct 35 ms 22608 KB Output is correct
5 Correct 33 ms 22600 KB Output is correct
6 Correct 65 ms 22344 KB Output is correct
7 Correct 25 ms 20972 KB Output is correct
8 Correct 238 ms 39096 KB Output is correct
9 Correct 242 ms 39096 KB Output is correct
10 Correct 21 ms 20988 KB Output is correct
11 Correct 178 ms 35924 KB Output is correct
12 Correct 177 ms 35912 KB Output is correct
13 Correct 319 ms 45728 KB Output is correct
14 Correct 22 ms 20972 KB Output is correct
15 Correct 304 ms 35912 KB Output is correct
16 Correct 157 ms 33316 KB Output is correct
17 Correct 159 ms 33352 KB Output is correct
18 Correct 161 ms 33764 KB Output is correct
19 Correct 365 ms 40776 KB Output is correct
20 Correct 339 ms 40660 KB Output is correct
21 Correct 284 ms 38196 KB Output is correct
22 Correct 257 ms 35860 KB Output is correct
23 Correct 168 ms 32776 KB Output is correct
24 Correct 161 ms 32840 KB Output is correct
25 Correct 258 ms 37400 KB Output is correct
26 Correct 159 ms 32844 KB Output is correct
27 Correct 152 ms 33872 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19940 KB Output is correct
2 Correct 36 ms 22352 KB Output is correct
3 Correct 43 ms 21320 KB Output is correct
4 Correct 35 ms 22608 KB Output is correct
5 Correct 33 ms 22600 KB Output is correct
6 Correct 65 ms 22344 KB Output is correct
7 Correct 25 ms 20972 KB Output is correct
8 Correct 238 ms 39096 KB Output is correct
9 Correct 242 ms 39096 KB Output is correct
10 Correct 21 ms 20988 KB Output is correct
11 Correct 178 ms 35924 KB Output is correct
12 Correct 177 ms 35912 KB Output is correct
13 Correct 319 ms 45728 KB Output is correct
14 Correct 22 ms 20972 KB Output is correct
15 Correct 304 ms 35912 KB Output is correct
16 Correct 157 ms 33316 KB Output is correct
17 Correct 159 ms 33352 KB Output is correct
18 Correct 161 ms 33764 KB Output is correct
19 Correct 365 ms 40776 KB Output is correct
20 Correct 339 ms 40660 KB Output is correct
21 Correct 284 ms 38196 KB Output is correct
22 Correct 257 ms 35860 KB Output is correct
23 Correct 168 ms 32776 KB Output is correct
24 Correct 161 ms 32840 KB Output is correct
25 Correct 258 ms 37400 KB Output is correct
26 Correct 159 ms 32844 KB Output is correct
27 Correct 152 ms 33872 KB Output is correct
28 Incorrect 22 ms 20528 KB Extra information in the output file
29 Halted 0 ms 0 KB -