Submission #1290089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290089		jojeonghoon	Meetings (JOI19_meetings)	C++20	29 / 100	378 ms	924 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;


const int LM=2020;
set<int> G[LM];
int ch[LM], p[LM];

int sz[LM], ch2[LM];
void dfs(int x, int par=-1){
    sz[x]=1;
    p[x]=par;
    for(int i:G[x]){
        if(i!=par && !ch2[i]){
            dfs(i,x);
            sz[x] += sz[i];
        }
    }
}

void dfsCH(int x, int par){
    ch2[x]=1;
    for(int i:G[x]){
        if(i!=par && !ch2[i]){
            dfsCH(i,x);
        }
    }
}

void Solve(int N){
    G[0].insert(1);
    G[1].insert(0);
    ch[0]=1;
    ch[1]=1;
    
    for(int i=2; i<N; i++){
        if(ch[i]) continue;
        
        fill(ch2,ch2+N+1,0);
        
        while(1){
            int st=0;
            for(; !ch[st] || ch2[st]; st++);
            
            dfs(st);
            
            int M=st;
            for(int j=0; j<N; j++){
                //if(ch[j]) printf("%d %d *\n", j,sz[j]);
                if(!ch2[j] && ch[j] && j!=st && max(sz[st]-sz[M],sz[M]) >= max(sz[st]-sz[j],sz[j]) ){
                    M=j;
                }
            }
            
            //printf("%d %d\n",M,st);
            
            if(M==st){
                G[M].insert(i);
                G[i].insert(M);
                break;
            }
            
            int q = Query(i, M, p[M]);
            
            
            //printf("%d %d %d : %d*\n",i,M,p[M], q);
            
            if(q==M){
                dfsCH(p[M], M);
                continue;
            }
            
            if(q==p[M]){
                dfsCH(M, p[M]);
                /*
                for(int j=0; j<N; j++) printf("%d ", ch2[j]);
                printf("\n");
                 */
                continue;
            }
            
            
            G[M].erase(p[M]);
            G[p[M]].erase(M);
            
            G[M].insert(q);
            G[q].insert(M);
            G[p[M]].insert(q);
            G[q].insert(p[M]);
            
            if(q!=i){
                G[q].insert(i);
                G[i].insert(q);
                ch[q]=1;
            }
            
            break;
        }
        /*
        for(int i=0; i<N; i++){
            for(int j: G[i]) if(i<j) printf("%d %d\n",i,j);
        }
        cout<<'\n'<<'\n';
         
        */
        ch[i]=1;
    }
    /*
    for(int i=0; i<N; i++){
        for(int j: G[i]) if(i<j) printf("%d %d\n",i,j);
    }*/
    
    for(int i=0; i<N; i++){
        for(int j: G[i]) if(i<j) Bridge(i, j);
    }
}

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