oj.uz

Submission #655579

# Submission time Handle Problem Language Result Execution time Memory
655579 2022-11-04T18:43:20 Z 600Mihnea Inside information (BOI21_servers) C++17
50 / 100
 266 ms 97508 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 done[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;
                        done[vertex]=1;
                        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],last=-INF;
                        int init=vertex;
                        while (vertex){
                                ret++;
                                if(p[vertex]==0){
                                        break;
                                }
                                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-done[q1[i]];
                }
        }
        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:255:29: warning: unused variable 'init' [-Wunused-variable]
  255 |                         int init=vertex;
      |                             ^~~~
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:141:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |                 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 56 ms 22716 KB Output is correct
3 Correct 50 ms 22532 KB Output is correct
4 Correct 58 ms 22908 KB Output is correct
5 Correct 52 ms 22704 KB Output is correct
6 Correct 56 ms 22488 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 56 ms 22716 KB Output is correct
3 Correct 50 ms 22532 KB Output is correct
4 Correct 58 ms 22908 KB Output is correct
5 Correct 52 ms 22704 KB Output is correct
6 Correct 56 ms 22488 KB Output is correct
7 Incorrect 46 ms 20572 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 43 ms 20556 KB Output is correct
2 Correct 214 ms 79804 KB Output is correct
3 Correct 211 ms 79828 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 20556 KB Output is correct
2 Correct 214 ms 79804 KB Output is correct
3 Correct 211 ms 79828 KB Output is correct
4 Incorrect 44 ms 20684 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 41 ms 20456 KB Output is correct
2 Correct 215 ms 97108 KB Output is correct
3 Correct 222 ms 97100 KB Output is correct
4 Correct 200 ms 97508 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20456 KB Output is correct
2 Correct 215 ms 97108 KB Output is correct
3 Correct 222 ms 97100 KB Output is correct
4 Correct 200 ms 97508 KB Output is correct
5 Incorrect 40 ms 20568 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 46 ms 20564 KB Output is correct
2 Correct 222 ms 79476 KB Output is correct
3 Correct 198 ms 79268 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20564 KB Output is correct
2 Correct 222 ms 79476 KB Output is correct
3 Correct 198 ms 79268 KB Output is correct
4 Incorrect 43 ms 20556 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 40 ms 20496 KB Output is correct
2 Correct 233 ms 97156 KB Output is correct
3 Correct 217 ms 97184 KB Output is correct
4 Correct 217 ms 97500 KB Output is correct
5 Correct 47 ms 20552 KB Output is correct
6 Correct 196 ms 79516 KB Output is correct
7 Correct 207 ms 79260 KB Output is correct
8 Correct 266 ms 80360 KB Output is correct
9 Correct 228 ms 80168 KB Output is correct
10 Correct 242 ms 86068 KB Output is correct
11 Correct 261 ms 85100 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20496 KB Output is correct
2 Correct 233 ms 97156 KB Output is correct
3 Correct 217 ms 97184 KB Output is correct
4 Correct 217 ms 97500 KB Output is correct
5 Correct 47 ms 20552 KB Output is correct
6 Correct 196 ms 79516 KB Output is correct
7 Correct 207 ms 79260 KB Output is correct
8 Correct 266 ms 80360 KB Output is correct
9 Correct 228 ms 80168 KB Output is correct
10 Correct 242 ms 86068 KB Output is correct
11 Correct 261 ms 85100 KB Output is correct
12 Incorrect 40 ms 20660 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 49 ms 20456 KB Output is correct
2 Correct 68 ms 22728 KB Output is correct
3 Correct 50 ms 22476 KB Output is correct
4 Correct 58 ms 22816 KB Output is correct
5 Correct 52 ms 22724 KB Output is correct
6 Correct 57 ms 22424 KB Output is correct
7 Correct 43 ms 20556 KB Output is correct
8 Correct 205 ms 79796 KB Output is correct
9 Correct 226 ms 79796 KB Output is correct
10 Correct 39 ms 20592 KB Output is correct
11 Correct 214 ms 97160 KB Output is correct
12 Correct 223 ms 97148 KB Output is correct
13 Correct 195 ms 97504 KB Output is correct
14 Correct 43 ms 20564 KB Output is correct
15 Correct 198 ms 79560 KB Output is correct
16 Correct 200 ms 79272 KB Output is correct
17 Correct 247 ms 80372 KB Output is correct
18 Correct 243 ms 80292 KB Output is correct
19 Correct 238 ms 86172 KB Output is correct
20 Correct 247 ms 84976 KB Output is correct
21 Correct 224 ms 79788 KB Output is correct
22 Correct 238 ms 79892 KB Output is correct
23 Correct 220 ms 80132 KB Output is correct
24 Correct 250 ms 80180 KB Output is correct
25 Correct 234 ms 84496 KB Output is correct
26 Correct 210 ms 78580 KB Output is correct
27 Correct 192 ms 78124 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20456 KB Output is correct
2 Correct 68 ms 22728 KB Output is correct
3 Correct 50 ms 22476 KB Output is correct
4 Correct 58 ms 22816 KB Output is correct
5 Correct 52 ms 22724 KB Output is correct
6 Correct 57 ms 22424 KB Output is correct
7 Correct 43 ms 20556 KB Output is correct
8 Correct 205 ms 79796 KB Output is correct
9 Correct 226 ms 79796 KB Output is correct
10 Correct 39 ms 20592 KB Output is correct
11 Correct 214 ms 97160 KB Output is correct
12 Correct 223 ms 97148 KB Output is correct
13 Correct 195 ms 97504 KB Output is correct
14 Correct 43 ms 20564 KB Output is correct
15 Correct 198 ms 79560 KB Output is correct
16 Correct 200 ms 79272 KB Output is correct
17 Correct 247 ms 80372 KB Output is correct
18 Correct 243 ms 80292 KB Output is correct
19 Correct 238 ms 86172 KB Output is correct
20 Correct 247 ms 84976 KB Output is correct
21 Correct 224 ms 79788 KB Output is correct
22 Correct 238 ms 79892 KB Output is correct
23 Correct 220 ms 80132 KB Output is correct
24 Correct 250 ms 80180 KB Output is correct
25 Correct 234 ms 84496 KB Output is correct
26 Correct 210 ms 78580 KB Output is correct
27 Correct 192 ms 78124 KB Output is correct
28 Incorrect 46 ms 20592 KB Extra information in the output file
29 Halted 0 ms 0 KB -