oj.uz

Submission #655570

# Submission time Handle Problem Language Result Execution time Memory
655570 2022-11-04T18:09:31 Z 600Mihnea Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 97488 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);
///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;

        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];
                        assert(2<=vertex&&vertex<=n);
                        int last=+INF;
                        while (1) {
                                cnt[vertex]++;
                                if(p[vertex]&&idup[vertex]<last){
                                        last=idup[vertex];
                                        vertex=p[vertex];
                                }else{
                                        break;
                                }
                        }

                }
                if (q1[i]){
                        assert(tp[i]==3);
                        int vertex=q1[i];
                        int ret=cnt[vertex]+1,last=-INF;
                        int init=vertex;
                        while (p[vertex]){
                                if ((idup[vertex]<last)){
                                        break;
                                }
                                last=idup[vertex];
                                for (auto &it:gg[p[vertex]]){
                                        int vecin=it.first;
                                        if(vecin!=vertex && idup[vertex]<idup[vecin]){
                                                ret+=cnt[vecin];
                                        }
                                }
                                vertex=p[vertex];
                        }
                        sol[i]=ret;
                }
        }
        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:253:29: warning: unused variable 'init' [-Wunused-variable]
  253 |                         int init=vertex;
      |                             ^~~~
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("them.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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("output2.txt","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:140:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |                 freopen("___input___.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20556 KB Output is correct
2 Correct 59 ms 22648 KB Output is correct
3 Correct 52 ms 22564 KB Output is correct
4 Correct 63 ms 22900 KB Output is correct
5 Correct 54 ms 22716 KB Output is correct
6 Correct 54 ms 22460 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20556 KB Output is correct
2 Correct 59 ms 22648 KB Output is correct
3 Correct 52 ms 22564 KB Output is correct
4 Correct 63 ms 22900 KB Output is correct
5 Correct 54 ms 22716 KB Output is correct
6 Correct 54 ms 22460 KB Output is correct
7 Incorrect 44 ms 20588 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 44 ms 20536 KB Output is correct
2 Correct 213 ms 79744 KB Output is correct
3 Correct 213 ms 79720 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20536 KB Output is correct
2 Correct 213 ms 79744 KB Output is correct
3 Correct 213 ms 79720 KB Output is correct
4 Correct 53 ms 20624 KB Output is correct
5 Execution timed out 3548 ms 80488 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20556 KB Output is correct
2 Correct 216 ms 97124 KB Output is correct
3 Correct 227 ms 97244 KB Output is correct
4 Correct 210 ms 97488 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20556 KB Output is correct
2 Correct 216 ms 97124 KB Output is correct
3 Correct 227 ms 97244 KB Output is correct
4 Correct 210 ms 97488 KB Output is correct
5 Incorrect 48 ms 21552 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 45 ms 20452 KB Output is correct
2 Correct 209 ms 79444 KB Output is correct
3 Correct 213 ms 79308 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20452 KB Output is correct
2 Correct 209 ms 79444 KB Output is correct
3 Correct 213 ms 79308 KB Output is correct
4 Incorrect 44 ms 20548 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 20556 KB Output is correct
2 Correct 224 ms 97096 KB Output is correct
3 Correct 223 ms 97100 KB Output is correct
4 Correct 206 ms 97484 KB Output is correct
5 Correct 45 ms 21344 KB Output is correct
6 Correct 205 ms 82764 KB Output is correct
7 Correct 206 ms 82628 KB Output is correct
8 Correct 262 ms 83540 KB Output is correct
9 Correct 239 ms 83588 KB Output is correct
10 Correct 237 ms 89708 KB Output is correct
11 Correct 248 ms 88372 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20556 KB Output is correct
2 Correct 224 ms 97096 KB Output is correct
3 Correct 223 ms 97100 KB Output is correct
4 Correct 206 ms 97484 KB Output is correct
5 Correct 45 ms 21344 KB Output is correct
6 Correct 205 ms 82764 KB Output is correct
7 Correct 206 ms 82628 KB Output is correct
8 Correct 262 ms 83540 KB Output is correct
9 Correct 239 ms 83588 KB Output is correct
10 Correct 237 ms 89708 KB Output is correct
11 Correct 248 ms 88372 KB Output is correct
12 Incorrect 41 ms 21548 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 20560 KB Output is correct
2 Correct 63 ms 22716 KB Output is correct
3 Correct 55 ms 22540 KB Output is correct
4 Correct 59 ms 22832 KB Output is correct
5 Correct 51 ms 22820 KB Output is correct
6 Correct 54 ms 22552 KB Output is correct
7 Correct 44 ms 20576 KB Output is correct
8 Correct 222 ms 79732 KB Output is correct
9 Correct 239 ms 79720 KB Output is correct
10 Correct 42 ms 20556 KB Output is correct
11 Correct 227 ms 97128 KB Output is correct
12 Correct 248 ms 97104 KB Output is correct
13 Correct 206 ms 97480 KB Output is correct
14 Correct 45 ms 21368 KB Output is correct
15 Correct 211 ms 82740 KB Output is correct
16 Correct 208 ms 82544 KB Output is correct
17 Correct 249 ms 83576 KB Output is correct
18 Correct 232 ms 83424 KB Output is correct
19 Correct 231 ms 89536 KB Output is correct
20 Correct 249 ms 88304 KB Output is correct
21 Correct 240 ms 83112 KB Output is correct
22 Correct 231 ms 83116 KB Output is correct
23 Correct 237 ms 83456 KB Output is correct
24 Correct 233 ms 83544 KB Output is correct
25 Correct 236 ms 87660 KB Output is correct
26 Correct 207 ms 81844 KB Output is correct
27 Correct 213 ms 81568 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20560 KB Output is correct
2 Correct 63 ms 22716 KB Output is correct
3 Correct 55 ms 22540 KB Output is correct
4 Correct 59 ms 22832 KB Output is correct
5 Correct 51 ms 22820 KB Output is correct
6 Correct 54 ms 22552 KB Output is correct
7 Correct 44 ms 20576 KB Output is correct
8 Correct 222 ms 79732 KB Output is correct
9 Correct 239 ms 79720 KB Output is correct
10 Correct 42 ms 20556 KB Output is correct
11 Correct 227 ms 97128 KB Output is correct
12 Correct 248 ms 97104 KB Output is correct
13 Correct 206 ms 97480 KB Output is correct
14 Correct 45 ms 21368 KB Output is correct
15 Correct 211 ms 82740 KB Output is correct
16 Correct 208 ms 82544 KB Output is correct
17 Correct 249 ms 83576 KB Output is correct
18 Correct 232 ms 83424 KB Output is correct
19 Correct 231 ms 89536 KB Output is correct
20 Correct 249 ms 88304 KB Output is correct
21 Correct 240 ms 83112 KB Output is correct
22 Correct 231 ms 83116 KB Output is correct
23 Correct 237 ms 83456 KB Output is correct
24 Correct 233 ms 83544 KB Output is correct
25 Correct 236 ms 87660 KB Output is correct
26 Correct 207 ms 81844 KB Output is correct
27 Correct 213 ms 81568 KB Output is correct
28 Incorrect 46 ms 21508 KB Extra information in the output file
29 Halted 0 ms 0 KB -