oj.uz

답안 #655553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655553 2022-11-04T17:39:33 Z 600Mihnea Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 89808 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;
    for (auto &it : gg[a])
    {
        int b=it.first;
        int i=it.second;

        if (b==par){
                continue;
        }
        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;
    }
}

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(1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
else freopen("___input___.txt","r",stdin);

        cin>>n>>k;

        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"){
                        int a;
                        cin>>a;
                        q1[i]=a;
                        sol[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;i++){
                if(tp[i]==2){
                        cnt_2++;
                        /// add edge
                        int vertex=who_has_id[i];
                        assert(2<=vertex&&vertex<=n);
                        while (1) {
                                cnt[vertex]++;
                                if(p[vertex]&&idup[p[vertex]]<idup[vertex]){
                                        vertex=p[vertex];
                                }else{
                                        break;
                                }
                        }

                }
                if (q1[i]){
                        int vertex=q1[i];
                        assert(tp[i]==0);
                        int ret=cnt[vertex]+1,last=-INF;
                        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;
                }else{
                        assert(tp[i]!=0);
                }
        }
        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);
                        if(sol[i]==1){
                                cout<<"yes\n";
                        }else{
                                cout<<"no\n";
                        }
                }
                if (q1[i]){
                        cout<<sol[i]<<"\n";
                }
        }

        return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:117:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 | else freopen("___input___.txt","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 20556 KB Output is correct
2 Correct 58 ms 24048 KB Output is correct
3 Correct 52 ms 23852 KB Output is correct
4 Correct 59 ms 24212 KB Output is correct
5 Correct 54 ms 23920 KB Output is correct
6 Correct 55 ms 23756 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 20556 KB Output is correct
2 Correct 58 ms 24048 KB Output is correct
3 Correct 52 ms 23852 KB Output is correct
4 Correct 59 ms 24212 KB Output is correct
5 Correct 54 ms 23920 KB Output is correct
6 Correct 55 ms 23756 KB Output is correct
7 Incorrect 43 ms 21424 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 20576 KB Output is correct
2 Correct 239 ms 82988 KB Output is correct
3 Correct 213 ms 82968 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 20576 KB Output is correct
2 Correct 239 ms 82988 KB Output is correct
3 Correct 213 ms 82968 KB Output is correct
4 Correct 46 ms 21580 KB Output is correct
5 Execution timed out 3545 ms 83048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 20556 KB Output is correct
2 Correct 232 ms 89596 KB Output is correct
3 Correct 229 ms 89808 KB Output is correct
4 Execution timed out 3560 ms 89292 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 20556 KB Output is correct
2 Correct 232 ms 89596 KB Output is correct
3 Correct 229 ms 89808 KB Output is correct
4 Execution timed out 3560 ms 89292 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 20440 KB Output is correct
2 Correct 217 ms 83196 KB Output is correct
3 Correct 199 ms 83020 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 20440 KB Output is correct
2 Correct 217 ms 83196 KB Output is correct
3 Correct 199 ms 83020 KB Output is correct
4 Incorrect 46 ms 21428 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 20560 KB Output is correct
2 Correct 228 ms 89808 KB Output is correct
3 Correct 221 ms 89676 KB Output is correct
4 Execution timed out 3572 ms 89516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 20560 KB Output is correct
2 Correct 228 ms 89808 KB Output is correct
3 Correct 221 ms 89676 KB Output is correct
4 Execution timed out 3572 ms 89516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 20560 KB Output is correct
2 Correct 68 ms 24140 KB Output is correct
3 Correct 53 ms 23808 KB Output is correct
4 Correct 61 ms 24120 KB Output is correct
5 Correct 55 ms 24012 KB Output is correct
6 Correct 57 ms 23812 KB Output is correct
7 Correct 46 ms 21344 KB Output is correct
8 Correct 215 ms 82888 KB Output is correct
9 Correct 216 ms 83008 KB Output is correct
10 Correct 41 ms 21388 KB Output is correct
11 Correct 220 ms 89568 KB Output is correct
12 Correct 212 ms 89636 KB Output is correct
13 Execution timed out 3513 ms 89408 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 20560 KB Output is correct
2 Correct 68 ms 24140 KB Output is correct
3 Correct 53 ms 23808 KB Output is correct
4 Correct 61 ms 24120 KB Output is correct
5 Correct 55 ms 24012 KB Output is correct
6 Correct 57 ms 23812 KB Output is correct
7 Correct 46 ms 21344 KB Output is correct
8 Correct 215 ms 82888 KB Output is correct
9 Correct 216 ms 83008 KB Output is correct
10 Correct 41 ms 21388 KB Output is correct
11 Correct 220 ms 89568 KB Output is correct
12 Correct 212 ms 89636 KB Output is correct
13 Execution timed out 3513 ms 89408 KB Time limit exceeded
14 Halted 0 ms 0 KB -