oj.uz

Submission #912574

# Submission time Handle Problem Language Result Execution time Memory
912574 2024-01-19T15:55:56 Z Ahmed57 Inside information (BOI21_servers) C++17
10 / 100
 3500 ms 313100 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[120005];
bool ss = 0;
int sz[120005];
int vis[120005];
map<int,pair<int,int>> aw[120005];
int dfs(int no,int pr){
    sz[no] = 1;
    for(auto i:adj[no]){
        if(i.first==pr||vis[i.first]!=0)continue;
        sz[no]+=dfs(i.first,no);
    }
    return sz[no];
}
int get_centroid(int no,int ss,int pr){
    for(auto i:adj[no]){
        if(pr==i.first||vis[i.first]!=0)continue;
        if(sz[i.first]*2>ss){
            return get_centroid(i.first,ss,no);
        }
    }
    return no;
}
vector<pair<pair<int,int>,pair<int,int>>> v[120005*2];
void calc(int i,int pr,int la,int ex,int nah,int le){
    v[la].push_back({{ex,nah},{i,le}});
    for(auto j:adj[i]){
        if((!(vis[j.first]||j.first==pr))&&j.second>la){
            calc(j.first,i,j.second,ex,nah,le);
        }
    }
}
map<int,pair<int,int>> mp[120005];
void calc2(int i,int pr,int la,int ex,int nah,int le,bool ss){
    if(ss)mp[ex][i] = {nah,le};
    else mp[ex][i] = {-1,-1};
    for(auto j:adj[i]){
        if((!(vis[j.first]||j.first==pr))&&j.second<la){
            calc2(j.first,i,j.second,ex,nah,le,ss);
        }else if(!(vis[j.first]||j.first==pr)){
            calc2(j.first,i,j.second,ex,nah,le,0);
        }
    }
}
vector<int> lol[120005],val[120005];
int pr[120005];
void centroid(int no,int par){
    int cen = get_centroid(no,dfs(no,-1),-1);
    pr[cen] = par;
    vis[cen] = 1;
    val[cen].push_back(0);
    for(auto i:adj[cen]){
        if(vis[i.first])continue;
        calc(i.first,-1,i.second,cen,i.second,i.first);
        calc2(i.first,-1,i.second,cen,i.first,i.second,1);
        lol[cen].push_back(i.second);
        val[cen].push_back(0);
    }
    for(auto i:adj[cen]){
        if(vis[i.first])continue;
        centroid(i.first,cen);
    }
}
void add(int x,int d){
    int it = lower_bound(lol[x].begin(),lol[x].end(),d)-lol[x].begin();
    it++;
    while(it<=lol[x].size()){
        val[x][it]++;
        it+=it&-it;
    }
}
int sum(int x,int d){
    int it = lower_bound(lol[x].begin(),lol[x].end(),d)-lol[x].begin();
    it++;it = min(it,(int)lol[x].size());
    int su = 0;
    while(it>=1){
        su+=val[x][it];
        it-=it&-it;
    }return su;
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,k;
    cin>>n>>k;
    k+=n-1;
    vector<vector<int>> qu;
    for(int i = 0;i<k;i++){
        char c;cin>>c;
        if(c=='S'){
            int a,b;cin>>a>>b;
            adj[a].push_back({b,i+1});
            adj[b].push_back({a,i+1});
            qu.push_back({-1});
        }else if(c=='C'){
            int d;cin>>d;
            qu.push_back({d});
        }else{
            int a,b;cin>>a>>b;
            qu.push_back({b,a});
        }
    }
    centroid(1,0);
    for(int i = 1;i<=n;i++){
        sort(lol[i].begin(),lol[i].end());
    }
    int xd = 1;
    for(auto i:qu){
        if(i[0]==-1){
            for(auto j:v[xd]){
                add(j.first.first,j.first.second);
                aw[j.first.first][j.second.first] = {j.second.second,j.first.second};
            }
        }else if(i.size()==1){
            int nn = i[0];
            long long all = 0;
            while(nn!=0){
                if(nn==i[0]){
                    all+=sum(nn,1e9);
                    all++;
                }else{
                    if(mp[nn][i[0]].first!=-1&&mp[nn][i[0]].second<=xd){
                        all+=sum(nn,1e9)-sum(nn,mp[nn][i[0]].second);
                        all++;
                    }
                }
                nn = pr[nn];
            }
            cout<<all<<endl;
        }else{
            if(i[0]==i[1]){
                cout<<"yes\n";
                xd++;
                continue;
            }
            int b = i[1];
            int nn = i[0];
            long long all = 0;
            bool sss = 0;
            while(nn!=0){
                if(nn==i[0]){
                    if(aw[nn][b].first!=0){
                        sss = 1;
                        break;
                    }
                }else{
                    if(nn==b&&mp[nn][i[0]].first!=-1&&mp[nn][i[0]].second<=xd){
                        sss = 1;break;
                    }
                    if(nn!=b&&mp[nn][i[0]].first!=-1&&aw[nn][b].first!=0&&aw[nn][b].first!=mp[nn][i[0]].first&&mp[nn][i[0]].second<aw[nn][b].second){
                        sss = 1; break ;
                    }
                }
                nn = pr[nn];
            }
            if(sss)cout<<"yes\n";
            else cout<<"no\n";
        }
        xd++;
    }

}

Compilation message

servers.cpp: In function 'void add(int, int)':
servers.cpp:68:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     while(it<=lol[x].size()){
      |           ~~^~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:139:23: warning: unused variable 'all' [-Wunused-variable]
  139 |             long long all = 0;
      |                       ^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 34044 KB Output is correct
2 Correct 281 ms 55204 KB Output is correct
3 Correct 157 ms 41980 KB Output is correct
4 Correct 360 ms 57148 KB Output is correct
5 Correct 353 ms 56108 KB Output is correct
6 Correct 159 ms 43944 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 34044 KB Output is correct
2 Correct 281 ms 55204 KB Output is correct
3 Correct 157 ms 41980 KB Output is correct
4 Correct 360 ms 57148 KB Output is correct
5 Correct 353 ms 56108 KB Output is correct
6 Correct 159 ms 43944 KB Output is correct
7 Correct 81 ms 35064 KB Output is correct
8 Correct 288 ms 47056 KB Output is correct
9 Correct 201 ms 39636 KB Output is correct
10 Correct 342 ms 48032 KB Output is correct
11 Correct 288 ms 47356 KB Output is correct
12 Correct 200 ms 40332 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 34304 KB Output is correct
2 Correct 624 ms 76792 KB Output is correct
3 Correct 565 ms 79112 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 34304 KB Output is correct
2 Correct 624 ms 76792 KB Output is correct
3 Correct 565 ms 79112 KB Output is correct
4 Correct 73 ms 34992 KB Output is correct
5 Correct 637 ms 77604 KB Output is correct
6 Correct 432 ms 70900 KB Output is correct
7 Correct 457 ms 71172 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 34048 KB Output is correct
2 Correct 1539 ms 191036 KB Output is correct
3 Correct 1539 ms 194220 KB Output is correct
4 Execution timed out 3571 ms 312796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 34048 KB Output is correct
2 Correct 1539 ms 191036 KB Output is correct
3 Correct 1539 ms 194220 KB Output is correct
4 Execution timed out 3571 ms 312796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 34056 KB Output is correct
2 Execution timed out 3573 ms 283728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 34056 KB Output is correct
2 Execution timed out 3573 ms 283728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 34040 KB Output is correct
2 Correct 1640 ms 191136 KB Output is correct
3 Correct 1744 ms 194444 KB Output is correct
4 Execution timed out 3544 ms 302044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 34040 KB Output is correct
2 Correct 1640 ms 191136 KB Output is correct
3 Correct 1744 ms 194444 KB Output is correct
4 Execution timed out 3544 ms 302044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 33988 KB Output is correct
2 Correct 362 ms 55028 KB Output is correct
3 Correct 182 ms 41944 KB Output is correct
4 Correct 433 ms 57168 KB Output is correct
5 Correct 351 ms 56052 KB Output is correct
6 Correct 182 ms 43844 KB Output is correct
7 Correct 66 ms 34812 KB Output is correct
8 Correct 648 ms 79068 KB Output is correct
9 Correct 606 ms 79120 KB Output is correct
10 Correct 76 ms 35068 KB Output is correct
11 Correct 1411 ms 194272 KB Output is correct
12 Correct 1422 ms 194316 KB Output is correct
13 Correct 3418 ms 313100 KB Output is correct
14 Correct 69 ms 34884 KB Output is correct
15 Correct 3316 ms 287224 KB Output is correct
16 Correct 1418 ms 182696 KB Output is correct
17 Correct 2814 ms 168480 KB Output is correct
18 Correct 1896 ms 158060 KB Output is correct
19 Correct 2284 ms 223804 KB Output is correct
20 Execution timed out 3581 ms 251164 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 33988 KB Output is correct
2 Correct 362 ms 55028 KB Output is correct
3 Correct 182 ms 41944 KB Output is correct
4 Correct 433 ms 57168 KB Output is correct
5 Correct 351 ms 56052 KB Output is correct
6 Correct 182 ms 43844 KB Output is correct
7 Correct 66 ms 34812 KB Output is correct
8 Correct 648 ms 79068 KB Output is correct
9 Correct 606 ms 79120 KB Output is correct
10 Correct 76 ms 35068 KB Output is correct
11 Correct 1411 ms 194272 KB Output is correct
12 Correct 1422 ms 194316 KB Output is correct
13 Correct 3418 ms 313100 KB Output is correct
14 Correct 69 ms 34884 KB Output is correct
15 Correct 3316 ms 287224 KB Output is correct
16 Correct 1418 ms 182696 KB Output is correct
17 Correct 2814 ms 168480 KB Output is correct
18 Correct 1896 ms 158060 KB Output is correct
19 Correct 2284 ms 223804 KB Output is correct
20 Execution timed out 3581 ms 251164 KB Time limit exceeded
21 Halted 0 ms 0 KB -