Submission #375108

#	Time	Username	Problem	Language	Result	Execution time	Memory
375108		jass921026	Meetings (JOI19_meetings)	C++14	29 / 100	283 ms	1644 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=302;
vector<int> G[MAXN], V[MAXN];
int LCA[MAXN][MAXN];
bool isRoot[MAXN];
void FindEdges(int x){
    for(auto i:V[x]) isRoot[i]=1;
    for(auto i:V[x]){
        for(auto j:V[x]){
            if(i!=j&&LCA[i][j]!=x&&LCA[i][j]!=i){
                isRoot[i]=0;
            }
        }
    }
    for(auto i:V[x]){
        if(isRoot[i]){
            G[x].push_back(i);
            for(auto j:V[x]){
                if(i!=j&&LCA[i][j]==i){
                    V[i].push_back(j);
                }
            }
        }
    }
}
void dfs(int x){
    FindEdges(x);
    for(auto i:G[x]){
        dfs(i);
    }
}
void Solve(int N) {
    for(int i=1;i<N;i++){
        for(int j=i+1;j<N;j++){
            int x=Query(0,i,j);
            LCA[i][j]=LCA[j][i]=x;
        }
    }
    for(int i=1;i<N;i++) V[0].push_back(i);
    dfs(0);
    for(int i=0;i<N;i++){
        for(auto j:G[i]){
            //cout<<i<<" "<<j<<"\n";
            int x=min(i,j), y=max(i,j);
            Bridge(x,y);
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71