oj.uz

Submission #655592

# Submission time Handle Problem Language Result Execution time Memory
655592 2022-11-04T19:34:10 Z 600Mihnea Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 97504 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=240000+7;
const int K = 20;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int,int>> q2[N];
int q1[N];
int p[N];
int pskip[K][N];
int dep[N];
int euler_tour[2 * N];
int tour_sz;
int first_time_on_tour[N];
int last_time_on_tour[N];
int lg2[2 * N];
int idup[N];
//vector<int> g[N];
pair<int, int> tab_lca[2 * N][K];
vector<int> who_have_id[N];
int who_has_id[N];

void dfs_lca(int a, int par = 0)
{
    p[a] = par;
    euler_tour[++tour_sz] = a;
    first_time_on_tour[a] = last_time_on_tour[a] = tour_sz;
    vector<pair<int, int>> ngg;
    for (auto &it : gg[a])
    {
        int b=it.first;
        int i=it.second;

        if (b==par){
                continue;
        }
        ngg.push_back(it);
        who_has_id[i]=b;
        idup[b]=i;
        dep[b] = 1 + dep[a];
        dfs_lca(b, a);
        euler_tour[++tour_sz] = a;
        last_time_on_tour[a] = tour_sz;
    }
    gg[a]=ngg;
}

void lcaTM()
{
    dfs_lca(1);
    for (int i = 2; i <= tour_sz; i++)
    {
        lg2[i] = 1 + lg2[i / 2];
    }
    for (int i = 1; i <= tour_sz; i++)
    {
        tab_lca[i][0] = {dep[euler_tour[i]], euler_tour[i]};
    }
    for (int k = 1; (1 << k) <= tour_sz; k++)
    {
        for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++)
        {
            tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int lca(int a, int b)
{
    if (first_time_on_tour[a] > last_time_on_tour[b])
    {
        swap(a, b);
    }
    a = first_time_on_tour[a];
    b = last_time_on_tour[b];
    int k = lg2[b - a + 1];
    return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second;
}

int goup(int a,int cnt){
        assert(cnt>=0);
        for(int i=0;i<K;i++){
                if(cnt&(1<<i)){
                        a=pskip[i][a];
                }
        }
        return a;
}

int sol[N];
int tp[N];
int inc[N];
int dcr[N];
int cnt[N];

void dfs2(int a){
        inc[a]=max(inc[a],1);
        dcr[a]=max(dcr[a],1);
        for (auto &it:gg[a]){
                int b=it.first;
                if(b==p[a]){
                        continue;
                }
                if(idup[a]<idup[b]){
                        inc[b]=1+inc[a];
                }else{
                        dcr[b]=1+dcr[a];
                }
                dfs2(b);
        }
        ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n";
}

bool home=0;

int main() {
        if(0){
                freopen("them.txt","r",stdin);
                freopen("output2.txt","w",stdout);
                /*char s[1000];
                while(cin.getline(s,1000)){
                        if(s[0]!='Q'){
                                cout<<s<<"\n";
                        }
                }*/
                string s;
                while(cin>>s){
                        if(s=="yes"||s=="no"){
                                continue;
                        }
                        cout<<s<<"\n";
                }

                exit(0);
        }
if(1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
else {
                home=1;
                freopen("___input___.txt","r",stdin);
               /// freopen("them.txt","r",stdin);
                if(0)freopen("out.txt","w",stdout);

}
        cin>>n>>k;

        int cnt3=0;
        for(int i=1;i<=n+k-1;i++){
                string s;
                cin>>s;
                assert(s=="S"||s=="Q"||s=="C");
                if(s=="S"){
                        tp[i]=2;
                        int a,b;
                        cin>>a>>b;
                        ///g[a].push_back(b);
                        ///g[b].push_back(a);
                        gg[a].push_back({b, i});
                        gg[b].push_back({a, i});
                        sol[i]=-1;
                }
                if(s=="Q"){
                        int a,b;
                        cin>>a>>b;
                        if(a==b){
                                tp[i]=1;
                                sol[i]=1;
                        }else{
                                q2[a].push_back({b, i});
                                tp[i]=1;
                                sol[i]=-2;
                        }
                }
                if(s=="C"){
                        cnt3++;
                        int a;
                        cin>>a;
                     ///   cout<<i<<" = "<<a<<"\n";
                        q1[i]=a;
                        sol[i]=-3;
                        tp[i]=3;
                }
        }

        lcaTM();
        dfs2(1);
        /// solve q1 for the general case

        for (int i=1;i<=n;i++){
                pskip[0][i]=p[i];
        }
        for (int k=1;k<K;k++){
                for (int i=1;i<=n;i++){
                        pskip[k][i]=pskip[k-1][pskip[k-1][i]];
                }
        }


        for (int a=1;a<=n;a++){
                for (auto &it:q2[a]){
                        int b=it.first,i=it.second;
                        /**

                        **/
                        /// drumul de la b la a e crescator?
                        vector<int> guys_x,guys_y;
                        int x=a,y=b,z;
                        swap(x,y);
                        z=lca(x,y);
                        int last=-1;
                        if(y!=z){
                                last=idup[y];
                        }else{
                                last=idup[goup(x,dep[x]-dep[z]-1)];
                        }
                        bool ok=1;
                        ok&=(inc[y]>=dep[y]-dep[z]);
                        ok&=(dcr[x]>=dep[x]-dep[z]);
                        if(x!=z&&y!=z){
                                ok&=(idup[goup(x,dep[x]-dep[z]-1)]<=idup[goup(y,dep[y]-dep[z]-1)]);
                        }
                        ok&=(last<i);
                        sol[i]=ok;
                }
        }

        const int INF=(int)1e9+7;

        int cnt_2=0;
        int ciq=0;

        for (int i=1;i<=n+k-1&&cnt3!=0;i++){
                if(tp[i]==2){
                        cnt_2++;
                        int cnt_down=max(1,inc[who_has_id[i]]-1);
                        int vertex=who_has_id[i];
                        for (int j=1;j<=cnt_down;j++){
                                cnt[vertex]++;
                                vertex=p[vertex];
                        }
                }
                if (q1[i]){
                        ciq++;
                        assert(tp[i]==3);
                        int vertex=q1[i];
                        int ret=1;

                        for (auto &it : gg[vertex]){
                                int v2=it.first;
                                ret+=cnt[v2];
                        }

                        int cnt_down=min(dcr[q1[i]],dep[q1[i]]);
                        int down=0;

                        for (int j=1;j<=cnt_down;j++){
                                ret+=(idup[vertex]<i);
                                for (auto &it:gg[p[vertex]]){
                                        int v2=it.first;
                                        if(idup[vertex]<idup[v2]){
                                                ret+=cnt[v2];
                                        }
                                }
                                vertex=p[vertex];
                        }
                        sol[i]=ret;
                }
        }
        if(cnt3){
                assert(cnt_2==n-1);
        }
unsigned long long h=0;
for(int i=1;i<=n+k-1;i++)h=7777*h+sol[i];
if(home){
        assert(h==8758581888253777949);
        cout<<"good\n";
        exit(0);
}
        for (int i=1;i<=n+k-1;i++){
                if(tp[i]==1){
                        assert(sol[i]==0||sol[i]==1);

                        ///continue;
                        if(sol[i]==1){
                                cout<<"yes\n";
                        }else{
                                cout<<"no\n";
                        }
                }
                if (tp[i]==3){
                        cout<<sol[i]<<"\n";
                }
        }

        return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:256:29: warning: unused variable 'down' [-Wunused-variable]
  256 |                         int down=0;
      |                             ^~~~
servers.cpp:229:19: warning: unused variable 'INF' [-Wunused-variable]
  229 |         const int INF=(int)1e9+7;
      |                   ^~~
servers.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen("them.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:122:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |                 freopen("output2.txt","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:142:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |                 freopen("___input___.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:144:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |                 if(0)freopen("out.txt","w",stdout);
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20480 KB Output is correct
2 Correct 58 ms 22832 KB Output is correct
3 Correct 51 ms 22532 KB Output is correct
4 Correct 61 ms 22908 KB Output is correct
5 Correct 51 ms 22732 KB Output is correct
6 Correct 53 ms 22508 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20480 KB Output is correct
2 Correct 58 ms 22832 KB Output is correct
3 Correct 51 ms 22532 KB Output is correct
4 Correct 61 ms 22908 KB Output is correct
5 Correct 51 ms 22732 KB Output is correct
6 Correct 53 ms 22508 KB Output is correct
7 Correct 47 ms 20556 KB Output is correct
8 Incorrect 55 ms 22396 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20556 KB Output is correct
2 Correct 215 ms 79788 KB Output is correct
3 Correct 225 ms 79780 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20556 KB Output is correct
2 Correct 215 ms 79788 KB Output is correct
3 Correct 225 ms 79780 KB Output is correct
4 Correct 42 ms 20604 KB Output is correct
5 Execution timed out 3603 ms 80440 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20556 KB Output is correct
2 Correct 218 ms 97144 KB Output is correct
3 Correct 225 ms 97172 KB Output is correct
4 Correct 196 ms 97436 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20556 KB Output is correct
2 Correct 218 ms 97144 KB Output is correct
3 Correct 225 ms 97172 KB Output is correct
4 Correct 196 ms 97436 KB Output is correct
5 Incorrect 40 ms 20640 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 48 ms 20472 KB Output is correct
2 Correct 216 ms 79508 KB Output is correct
3 Correct 207 ms 79260 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 20472 KB Output is correct
2 Correct 216 ms 79508 KB Output is correct
3 Correct 207 ms 79260 KB Output is correct
4 Incorrect 50 ms 20524 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 41 ms 20516 KB Output is correct
2 Correct 232 ms 97096 KB Output is correct
3 Correct 217 ms 97104 KB Output is correct
4 Correct 197 ms 97504 KB Output is correct
5 Correct 44 ms 20512 KB Output is correct
6 Correct 201 ms 79584 KB Output is correct
7 Correct 206 ms 79376 KB Output is correct
8 Correct 244 ms 80212 KB Output is correct
9 Correct 226 ms 80236 KB Output is correct
10 Correct 220 ms 86160 KB Output is correct
11 Correct 260 ms 85040 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20516 KB Output is correct
2 Correct 232 ms 97096 KB Output is correct
3 Correct 217 ms 97104 KB Output is correct
4 Correct 197 ms 97504 KB Output is correct
5 Correct 44 ms 20512 KB Output is correct
6 Correct 201 ms 79584 KB Output is correct
7 Correct 206 ms 79376 KB Output is correct
8 Correct 244 ms 80212 KB Output is correct
9 Correct 226 ms 80236 KB Output is correct
10 Correct 220 ms 86160 KB Output is correct
11 Correct 260 ms 85040 KB Output is correct
12 Incorrect 43 ms 20616 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 43 ms 20548 KB Output is correct
2 Correct 61 ms 22676 KB Output is correct
3 Correct 54 ms 22548 KB Output is correct
4 Correct 61 ms 22900 KB Output is correct
5 Correct 53 ms 22744 KB Output is correct
6 Correct 54 ms 22552 KB Output is correct
7 Correct 43 ms 20692 KB Output is correct
8 Correct 211 ms 79752 KB Output is correct
9 Correct 218 ms 79760 KB Output is correct
10 Correct 40 ms 20496 KB Output is correct
11 Correct 211 ms 97216 KB Output is correct
12 Correct 215 ms 97076 KB Output is correct
13 Correct 198 ms 97432 KB Output is correct
14 Correct 44 ms 20516 KB Output is correct
15 Correct 207 ms 79476 KB Output is correct
16 Correct 200 ms 79260 KB Output is correct
17 Correct 248 ms 80204 KB Output is correct
18 Correct 227 ms 80212 KB Output is correct
19 Correct 222 ms 86160 KB Output is correct
20 Correct 249 ms 85048 KB Output is correct
21 Correct 209 ms 79776 KB Output is correct
22 Correct 217 ms 79860 KB Output is correct
23 Correct 222 ms 80188 KB Output is correct
24 Correct 225 ms 80176 KB Output is correct
25 Correct 227 ms 84404 KB Output is correct
26 Correct 202 ms 78368 KB Output is correct
27 Correct 193 ms 78196 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20548 KB Output is correct
2 Correct 61 ms 22676 KB Output is correct
3 Correct 54 ms 22548 KB Output is correct
4 Correct 61 ms 22900 KB Output is correct
5 Correct 53 ms 22744 KB Output is correct
6 Correct 54 ms 22552 KB Output is correct
7 Correct 43 ms 20692 KB Output is correct
8 Correct 211 ms 79752 KB Output is correct
9 Correct 218 ms 79760 KB Output is correct
10 Correct 40 ms 20496 KB Output is correct
11 Correct 211 ms 97216 KB Output is correct
12 Correct 215 ms 97076 KB Output is correct
13 Correct 198 ms 97432 KB Output is correct
14 Correct 44 ms 20516 KB Output is correct
15 Correct 207 ms 79476 KB Output is correct
16 Correct 200 ms 79260 KB Output is correct
17 Correct 248 ms 80204 KB Output is correct
18 Correct 227 ms 80212 KB Output is correct
19 Correct 222 ms 86160 KB Output is correct
20 Correct 249 ms 85048 KB Output is correct
21 Correct 209 ms 79776 KB Output is correct
22 Correct 217 ms 79860 KB Output is correct
23 Correct 222 ms 80188 KB Output is correct
24 Correct 225 ms 80176 KB Output is correct
25 Correct 227 ms 84404 KB Output is correct
26 Correct 202 ms 78368 KB Output is correct
27 Correct 193 ms 78196 KB Output is correct
28 Correct 44 ms 20636 KB Output is correct
29 Incorrect 57 ms 22388 KB Extra information in the output file
30 Halted 0 ms 0 KB -