oj.uz

Submission #912584

# Submission time Handle Problem Language Result Execution time Memory
912584 2024-01-19T16:03:09 Z Ahmed57 Inside information (BOI21_servers) C++17
100 / 100
 2343 ms 243696 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
vector<pair<int,int>> adj[120005];
bool ss = 0;
int sz[120005];
int vis[120005];
unordered_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);
        }
    }
}
unordered_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:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     while(it<=lol[x].size()){
      |           ~~^~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:141:23: warning: unused variable 'all' [-Wunused-variable]
  141 |             long long all = 0;
      |                       ^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35840 KB Output is correct
2 Correct 160 ms 50680 KB Output is correct
3 Correct 70 ms 40612 KB Output is correct
4 Correct 195 ms 51248 KB Output is correct
5 Correct 135 ms 50528 KB Output is correct
6 Correct 66 ms 42044 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35840 KB Output is correct
2 Correct 160 ms 50680 KB Output is correct
3 Correct 70 ms 40612 KB Output is correct
4 Correct 195 ms 51248 KB Output is correct
5 Correct 135 ms 50528 KB Output is correct
6 Correct 66 ms 42044 KB Output is correct
7 Correct 47 ms 35840 KB Output is correct
8 Correct 95 ms 44540 KB Output is correct
9 Correct 67 ms 39392 KB Output is correct
10 Correct 112 ms 44916 KB Output is correct
11 Correct 94 ms 44572 KB Output is correct
12 Correct 56 ms 39420 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 35836 KB Output is correct
2 Correct 273 ms 76196 KB Output is correct
3 Correct 308 ms 76624 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 35836 KB Output is correct
2 Correct 273 ms 76196 KB Output is correct
3 Correct 308 ms 76624 KB Output is correct
4 Correct 36 ms 35848 KB Output is correct
5 Correct 242 ms 74744 KB Output is correct
6 Correct 165 ms 66544 KB Output is correct
7 Correct 169 ms 66268 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35840 KB Output is correct
2 Correct 801 ms 158092 KB Output is correct
3 Correct 813 ms 158036 KB Output is correct
4 Correct 1758 ms 243672 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35840 KB Output is correct
2 Correct 801 ms 158092 KB Output is correct
3 Correct 813 ms 158036 KB Output is correct
4 Correct 1758 ms 243672 KB Output is correct
5 Correct 44 ms 35800 KB Output is correct
6 Correct 897 ms 155380 KB Output is correct
7 Correct 1448 ms 221112 KB Output is correct
8 Correct 1014 ms 152376 KB Output is correct
9 Correct 1020 ms 152328 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35852 KB Output is correct
2 Correct 2343 ms 225068 KB Output is correct
3 Correct 918 ms 150024 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35852 KB Output is correct
2 Correct 2343 ms 225068 KB Output is correct
3 Correct 918 ms 150024 KB Output is correct
4 Correct 38 ms 35924 KB Output is correct
5 Correct 1706 ms 204172 KB Output is correct
6 Correct 996 ms 147752 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35772 KB Output is correct
2 Correct 914 ms 158200 KB Output is correct
3 Correct 948 ms 158664 KB Output is correct
4 Correct 1921 ms 243696 KB Output is correct
5 Correct 40 ms 35852 KB Output is correct
6 Correct 2304 ms 225088 KB Output is correct
7 Correct 937 ms 150048 KB Output is correct
8 Correct 1197 ms 140060 KB Output is correct
9 Correct 1027 ms 131180 KB Output is correct
10 Correct 1336 ms 180876 KB Output is correct
11 Correct 2044 ms 202112 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35772 KB Output is correct
2 Correct 914 ms 158200 KB Output is correct
3 Correct 948 ms 158664 KB Output is correct
4 Correct 1921 ms 243696 KB Output is correct
5 Correct 40 ms 35852 KB Output is correct
6 Correct 2304 ms 225088 KB Output is correct
7 Correct 937 ms 150048 KB Output is correct
8 Correct 1197 ms 140060 KB Output is correct
9 Correct 1027 ms 131180 KB Output is correct
10 Correct 1336 ms 180876 KB Output is correct
11 Correct 2044 ms 202112 KB Output is correct
12 Correct 38 ms 36612 KB Output is correct
13 Correct 990 ms 158812 KB Output is correct
14 Correct 1457 ms 224028 KB Output is correct
15 Correct 993 ms 155340 KB Output is correct
16 Correct 1040 ms 155032 KB Output is correct
17 Correct 42 ms 36608 KB Output is correct
18 Correct 1900 ms 207068 KB Output is correct
19 Correct 1030 ms 150784 KB Output is correct
20 Correct 1136 ms 135704 KB Output is correct
21 Correct 1022 ms 131832 KB Output is correct
22 Correct 1527 ms 170708 KB Output is correct
23 Correct 1616 ms 192580 KB Output is correct
24 Correct 1320 ms 188176 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35880 KB Output is correct
2 Correct 212 ms 50860 KB Output is correct
3 Correct 68 ms 40700 KB Output is correct
4 Correct 191 ms 51408 KB Output is correct
5 Correct 129 ms 50432 KB Output is correct
6 Correct 68 ms 41940 KB Output is correct
7 Correct 34 ms 36096 KB Output is correct
8 Correct 274 ms 76528 KB Output is correct
9 Correct 278 ms 76188 KB Output is correct
10 Correct 38 ms 36116 KB Output is correct
11 Correct 824 ms 158184 KB Output is correct
12 Correct 790 ms 158224 KB Output is correct
13 Correct 1659 ms 243684 KB Output is correct
14 Correct 38 ms 36100 KB Output is correct
15 Correct 2057 ms 225184 KB Output is correct
16 Correct 820 ms 150520 KB Output is correct
17 Correct 1107 ms 140252 KB Output is correct
18 Correct 928 ms 131236 KB Output is correct
19 Correct 1171 ms 180620 KB Output is correct
20 Correct 1932 ms 202184 KB Output is correct
21 Correct 404 ms 86264 KB Output is correct
22 Correct 454 ms 86764 KB Output is correct
23 Correct 771 ms 114724 KB Output is correct
24 Correct 839 ms 115856 KB Output is correct
25 Correct 858 ms 127884 KB Output is correct
26 Correct 626 ms 119236 KB Output is correct
27 Correct 564 ms 115632 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35880 KB Output is correct
2 Correct 212 ms 50860 KB Output is correct
3 Correct 68 ms 40700 KB Output is correct
4 Correct 191 ms 51408 KB Output is correct
5 Correct 129 ms 50432 KB Output is correct
6 Correct 68 ms 41940 KB Output is correct
7 Correct 34 ms 36096 KB Output is correct
8 Correct 274 ms 76528 KB Output is correct
9 Correct 278 ms 76188 KB Output is correct
10 Correct 38 ms 36116 KB Output is correct
11 Correct 824 ms 158184 KB Output is correct
12 Correct 790 ms 158224 KB Output is correct
13 Correct 1659 ms 243684 KB Output is correct
14 Correct 38 ms 36100 KB Output is correct
15 Correct 2057 ms 225184 KB Output is correct
16 Correct 820 ms 150520 KB Output is correct
17 Correct 1107 ms 140252 KB Output is correct
18 Correct 928 ms 131236 KB Output is correct
19 Correct 1171 ms 180620 KB Output is correct
20 Correct 1932 ms 202184 KB Output is correct
21 Correct 404 ms 86264 KB Output is correct
22 Correct 454 ms 86764 KB Output is correct
23 Correct 771 ms 114724 KB Output is correct
24 Correct 839 ms 115856 KB Output is correct
25 Correct 858 ms 127884 KB Output is correct
26 Correct 626 ms 119236 KB Output is correct
27 Correct 564 ms 115632 KB Output is correct
28 Correct 37 ms 36612 KB Output is correct
29 Correct 116 ms 45568 KB Output is correct
30 Correct 64 ms 40388 KB Output is correct
31 Correct 110 ms 46104 KB Output is correct
32 Correct 96 ms 45568 KB Output is correct
33 Correct 55 ms 40704 KB Output is correct
34 Correct 36 ms 36864 KB Output is correct
35 Correct 246 ms 77468 KB Output is correct
36 Correct 158 ms 67800 KB Output is correct
37 Correct 189 ms 68200 KB Output is correct
38 Correct 39 ms 36768 KB Output is correct
39 Correct 900 ms 158440 KB Output is correct
40 Correct 1380 ms 224756 KB Output is correct
41 Correct 1008 ms 155540 KB Output is correct
42 Correct 917 ms 155352 KB Output is correct
43 Correct 39 ms 37064 KB Output is correct
44 Correct 1672 ms 207744 KB Output is correct
45 Correct 978 ms 151048 KB Output is correct
46 Correct 986 ms 135668 KB Output is correct
47 Correct 962 ms 131996 KB Output is correct
48 Correct 1315 ms 171144 KB Output is correct
49 Correct 1542 ms 192944 KB Output is correct
50 Correct 1199 ms 188236 KB Output is correct
51 Correct 213 ms 76276 KB Output is correct
52 Correct 212 ms 69488 KB Output is correct
53 Correct 174 ms 69124 KB Output is correct
54 Correct 169 ms 69104 KB Output is correct
55 Correct 201 ms 71492 KB Output is correct
56 Correct 602 ms 110200 KB Output is correct
57 Correct 587 ms 117808 KB Output is correct
58 Correct 992 ms 119316 KB Output is correct
59 Correct 607 ms 115212 KB Output is correct