oj.uz

Submission #912581

# Submission time Handle Problem Language Result Execution time Memory
912581 2024-01-19T16:00:12 Z Ahmed57 Inside information (BOI21_servers) C++17
40 / 100
 3500 ms 311512 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(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //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<<"\n";
        }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:140:23: warning: unused variable 'all' [-Wunused-variable]
  140 |             long long all = 0;
      |                       ^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34808 KB Output is correct
2 Correct 294 ms 56164 KB Output is correct
3 Correct 135 ms 41560 KB Output is correct
4 Correct 357 ms 56832 KB Output is correct
5 Correct 352 ms 55984 KB Output is correct
6 Correct 135 ms 43648 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34808 KB Output is correct
2 Correct 294 ms 56164 KB Output is correct
3 Correct 135 ms 41560 KB Output is correct
4 Correct 357 ms 56832 KB Output is correct
5 Correct 352 ms 55984 KB Output is correct
6 Correct 135 ms 43648 KB Output is correct
7 Correct 48 ms 34824 KB Output is correct
8 Correct 182 ms 46840 KB Output is correct
9 Correct 110 ms 39396 KB Output is correct
10 Correct 241 ms 47604 KB Output is correct
11 Correct 209 ms 46964 KB Output is correct
12 Correct 93 ms 39824 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35052 KB Output is correct
2 Correct 547 ms 78144 KB Output is correct
3 Correct 528 ms 78256 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35052 KB Output is correct
2 Correct 547 ms 78144 KB Output is correct
3 Correct 528 ms 78256 KB Output is correct
4 Correct 43 ms 34816 KB Output is correct
5 Correct 544 ms 76308 KB Output is correct
6 Correct 285 ms 70504 KB Output is correct
7 Correct 265 ms 70360 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 34820 KB Output is correct
2 Correct 1342 ms 192692 KB Output is correct
3 Correct 1289 ms 192752 KB Output is correct
4 Correct 3189 ms 311284 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 34820 KB Output is correct
2 Correct 1342 ms 192692 KB Output is correct
3 Correct 1289 ms 192752 KB Output is correct
4 Correct 3189 ms 311284 KB Output is correct
5 Correct 49 ms 34816 KB Output is correct
6 Correct 1953 ms 190888 KB Output is correct
7 Correct 3076 ms 280740 KB Output is correct
8 Correct 2342 ms 187692 KB Output is correct
9 Correct 2441 ms 187404 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34940 KB Output is correct
2 Correct 3088 ms 285500 KB Output is correct
3 Correct 1179 ms 182344 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34940 KB Output is correct
2 Correct 3088 ms 285500 KB Output is correct
3 Correct 1179 ms 182344 KB Output is correct
4 Correct 46 ms 34820 KB Output is correct
5 Correct 2784 ms 257500 KB Output is correct
6 Correct 1764 ms 180240 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34844 KB Output is correct
2 Correct 1280 ms 192660 KB Output is correct
3 Correct 1329 ms 192748 KB Output is correct
4 Correct 3190 ms 311512 KB Output is correct
5 Correct 45 ms 35052 KB Output is correct
6 Correct 3114 ms 287060 KB Output is correct
7 Correct 1224 ms 183104 KB Output is correct
8 Correct 2229 ms 168452 KB Output is correct
9 Correct 1488 ms 158256 KB Output is correct
10 Correct 1788 ms 223796 KB Output is correct
11 Execution timed out 3590 ms 255292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34844 KB Output is correct
2 Correct 1280 ms 192660 KB Output is correct
3 Correct 1329 ms 192748 KB Output is correct
4 Correct 3190 ms 311512 KB Output is correct
5 Correct 45 ms 35052 KB Output is correct
6 Correct 3114 ms 287060 KB Output is correct
7 Correct 1224 ms 183104 KB Output is correct
8 Correct 2229 ms 168452 KB Output is correct
9 Correct 1488 ms 158256 KB Output is correct
10 Correct 1788 ms 223796 KB Output is correct
11 Execution timed out 3590 ms 255292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 35004 KB Output is correct
2 Correct 319 ms 56148 KB Output is correct
3 Correct 127 ms 41492 KB Output is correct
4 Correct 343 ms 56828 KB Output is correct
5 Correct 307 ms 55992 KB Output is correct
6 Correct 133 ms 43648 KB Output is correct
7 Correct 45 ms 34736 KB Output is correct
8 Correct 544 ms 78712 KB Output is correct
9 Correct 525 ms 78256 KB Output is correct
10 Correct 45 ms 34808 KB Output is correct
11 Correct 1252 ms 192460 KB Output is correct
12 Correct 1271 ms 192900 KB Output is correct
13 Correct 3121 ms 311444 KB Output is correct
14 Correct 43 ms 34872 KB Output is correct
15 Correct 2972 ms 285800 KB Output is correct
16 Correct 1194 ms 180924 KB Output is correct
17 Correct 2233 ms 167180 KB Output is correct
18 Correct 1546 ms 156692 KB Output is correct
19 Correct 2005 ms 222856 KB Output is correct
20 Execution timed out 3531 ms 253908 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 35004 KB Output is correct
2 Correct 319 ms 56148 KB Output is correct
3 Correct 127 ms 41492 KB Output is correct
4 Correct 343 ms 56828 KB Output is correct
5 Correct 307 ms 55992 KB Output is correct
6 Correct 133 ms 43648 KB Output is correct
7 Correct 45 ms 34736 KB Output is correct
8 Correct 544 ms 78712 KB Output is correct
9 Correct 525 ms 78256 KB Output is correct
10 Correct 45 ms 34808 KB Output is correct
11 Correct 1252 ms 192460 KB Output is correct
12 Correct 1271 ms 192900 KB Output is correct
13 Correct 3121 ms 311444 KB Output is correct
14 Correct 43 ms 34872 KB Output is correct
15 Correct 2972 ms 285800 KB Output is correct
16 Correct 1194 ms 180924 KB Output is correct
17 Correct 2233 ms 167180 KB Output is correct
18 Correct 1546 ms 156692 KB Output is correct
19 Correct 2005 ms 222856 KB Output is correct
20 Execution timed out 3531 ms 253908 KB Time limit exceeded
21 Halted 0 ms 0 KB -