oj.uz

Submission #655589

# Submission time Handle Problem Language Result Execution time Memory
655589 2022-11-04T19:24:53 Z 600Mihnea Inside information (BOI21_servers) C++17
62.5 / 100
 3500 ms 100600 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";
}

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 {
                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;

//        assert(p[2]==21);
 //       assert(p[25]==21);

       // cout<<"sir = "<<idup[46]<<" "<<idup[2]<<" "<<idup[21]<<"\n";
        for (int i=1;i<=n+k-1&&cnt3!=0;i++){
                if(tp[i]==2){
                        cnt_2++;
                        /// add edge
                        int vertex=who_has_id[i],last=+INF;

                      //  cout<<vertex<<" "<<p[vertex]<<"\n";


                        while(p[vertex]){
                                if(idup[vertex]>last){
                                        break;
                                }
                                last=idup[vertex];
                                cnt[vertex]++;

                                vertex=p[vertex];
                        }
                }
                if (q1[i]){
                        ciq++;
                        assert(tp[i]==3);
                        int vertex=q1[i];
                        int ret=1,last=-INF;
                        int init=vertex;

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

                        while (p[vertex]){
                                if (idup[vertex]<last){
                                        break;
                                }
                                ret+=(idup[vertex]<i);
                                for (auto &it:gg[p[vertex]]){
                                        int v2=it.first;
                                        if(idup[vertex]<idup[v2]){
                                                ret+=cnt[v2];
                                        }
                                }
                                last=idup[vertex];
                                vertex=p[vertex];
                        }

                        sol[i]=ret;

                        if(ciq==194){
                           //     cout<<"ret = "<<ret<<", query = "<<init<<"\n";
                           //    return 0;
                        }
                }
        }
        if(cnt3)
        assert(cnt_2==n-1);


        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:259:29: warning: unused variable 'init' [-Wunused-variable]
  259 |                         int init=vertex;
      |                             ^~~~
servers.cpp:119:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                 freopen("them.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen("output2.txt","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:139:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |                 freopen("___input___.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:141:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |                 if(0)freopen("out.txt","w",stdout);
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20556 KB Output is correct
2 Correct 56 ms 22768 KB Output is correct
3 Correct 51 ms 22512 KB Output is correct
4 Correct 65 ms 22860 KB Output is correct
5 Correct 51 ms 22728 KB Output is correct
6 Correct 54 ms 22480 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20556 KB Output is correct
2 Correct 56 ms 22768 KB Output is correct
3 Correct 51 ms 22512 KB Output is correct
4 Correct 65 ms 22860 KB Output is correct
5 Correct 51 ms 22728 KB Output is correct
6 Correct 54 ms 22480 KB Output is correct
7 Correct 48 ms 20548 KB Output is correct
8 Correct 62 ms 23520 KB Output is correct
9 Correct 81 ms 23448 KB Output is correct
10 Correct 57 ms 23644 KB Output is correct
11 Correct 50 ms 23540 KB Output is correct
12 Correct 257 ms 23356 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20584 KB Output is correct
2 Correct 230 ms 79724 KB Output is correct
3 Correct 219 ms 79776 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 20584 KB Output is correct
2 Correct 230 ms 79724 KB Output is correct
3 Correct 219 ms 79776 KB Output is correct
4 Correct 49 ms 20556 KB Output is correct
5 Execution timed out 3558 ms 80452 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20468 KB Output is correct
2 Correct 254 ms 97156 KB Output is correct
3 Correct 209 ms 97140 KB Output is correct
4 Correct 195 ms 97584 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20468 KB Output is correct
2 Correct 254 ms 97156 KB Output is correct
3 Correct 209 ms 97140 KB Output is correct
4 Correct 195 ms 97584 KB Output is correct
5 Correct 51 ms 20648 KB Output is correct
6 Correct 226 ms 100600 KB Output is correct
7 Execution timed out 3550 ms 100460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 20548 KB Output is correct
2 Correct 211 ms 79480 KB Output is correct
3 Correct 227 ms 79304 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 20548 KB Output is correct
2 Correct 211 ms 79480 KB Output is correct
3 Correct 227 ms 79304 KB Output is correct
4 Correct 44 ms 20588 KB Output is correct
5 Correct 191 ms 82848 KB Output is correct
6 Correct 210 ms 82640 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20616 KB Output is correct
2 Correct 218 ms 97160 KB Output is correct
3 Correct 229 ms 97280 KB Output is correct
4 Correct 204 ms 97480 KB Output is correct
5 Correct 55 ms 20496 KB Output is correct
6 Correct 205 ms 79480 KB Output is correct
7 Correct 214 ms 79256 KB Output is correct
8 Correct 259 ms 80272 KB Output is correct
9 Correct 234 ms 80224 KB Output is correct
10 Correct 252 ms 86208 KB Output is correct
11 Correct 256 ms 85004 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20616 KB Output is correct
2 Correct 218 ms 97160 KB Output is correct
3 Correct 229 ms 97280 KB Output is correct
4 Correct 204 ms 97480 KB Output is correct
5 Correct 55 ms 20496 KB Output is correct
6 Correct 205 ms 79480 KB Output is correct
7 Correct 214 ms 79256 KB Output is correct
8 Correct 259 ms 80272 KB Output is correct
9 Correct 234 ms 80224 KB Output is correct
10 Correct 252 ms 86208 KB Output is correct
11 Correct 256 ms 85004 KB Output is correct
12 Correct 42 ms 20540 KB Output is correct
13 Correct 284 ms 100532 KB Output is correct
14 Execution timed out 3567 ms 100424 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20516 KB Output is correct
2 Correct 58 ms 22740 KB Output is correct
3 Correct 55 ms 22456 KB Output is correct
4 Correct 80 ms 22824 KB Output is correct
5 Correct 53 ms 22796 KB Output is correct
6 Correct 54 ms 22492 KB Output is correct
7 Correct 45 ms 20472 KB Output is correct
8 Correct 218 ms 79812 KB Output is correct
9 Correct 236 ms 79796 KB Output is correct
10 Correct 41 ms 20484 KB Output is correct
11 Correct 249 ms 97052 KB Output is correct
12 Correct 227 ms 97448 KB Output is correct
13 Correct 202 ms 97484 KB Output is correct
14 Correct 55 ms 20508 KB Output is correct
15 Correct 203 ms 79564 KB Output is correct
16 Correct 216 ms 79228 KB Output is correct
17 Correct 260 ms 80204 KB Output is correct
18 Correct 241 ms 80356 KB Output is correct
19 Correct 247 ms 86168 KB Output is correct
20 Correct 256 ms 85044 KB Output is correct
21 Correct 247 ms 79868 KB Output is correct
22 Correct 256 ms 79808 KB Output is correct
23 Correct 234 ms 80188 KB Output is correct
24 Correct 264 ms 80264 KB Output is correct
25 Correct 233 ms 84444 KB Output is correct
26 Correct 220 ms 78468 KB Output is correct
27 Correct 211 ms 78284 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20516 KB Output is correct
2 Correct 58 ms 22740 KB Output is correct
3 Correct 55 ms 22456 KB Output is correct
4 Correct 80 ms 22824 KB Output is correct
5 Correct 53 ms 22796 KB Output is correct
6 Correct 54 ms 22492 KB Output is correct
7 Correct 45 ms 20472 KB Output is correct
8 Correct 218 ms 79812 KB Output is correct
9 Correct 236 ms 79796 KB Output is correct
10 Correct 41 ms 20484 KB Output is correct
11 Correct 249 ms 97052 KB Output is correct
12 Correct 227 ms 97448 KB Output is correct
13 Correct 202 ms 97484 KB Output is correct
14 Correct 55 ms 20508 KB Output is correct
15 Correct 203 ms 79564 KB Output is correct
16 Correct 216 ms 79228 KB Output is correct
17 Correct 260 ms 80204 KB Output is correct
18 Correct 241 ms 80356 KB Output is correct
19 Correct 247 ms 86168 KB Output is correct
20 Correct 256 ms 85044 KB Output is correct
21 Correct 247 ms 79868 KB Output is correct
22 Correct 256 ms 79808 KB Output is correct
23 Correct 234 ms 80188 KB Output is correct
24 Correct 264 ms 80264 KB Output is correct
25 Correct 233 ms 84444 KB Output is correct
26 Correct 220 ms 78468 KB Output is correct
27 Correct 211 ms 78284 KB Output is correct
28 Correct 46 ms 20616 KB Output is correct
29 Correct 57 ms 23564 KB Output is correct
30 Correct 82 ms 23448 KB Output is correct
31 Correct 61 ms 23680 KB Output is correct
32 Correct 50 ms 23500 KB Output is correct
33 Correct 250 ms 23356 KB Output is correct
34 Correct 49 ms 21452 KB Output is correct
35 Execution timed out 3545 ms 83172 KB Time limit exceeded
36 Halted 0 ms 0 KB -