Submission #369906

#	Time	Username	Problem	Language	Result	Execution time	Memory
369906		azberjibiou	Meetings (JOI19_meetings)	C++17	29 / 100	2039 ms	896 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
const int mxN=2020;
vector <int> v[mxN], g[mxN];
bool Chk[mxN];
bool used[mxN];
int sub[mxN];
int msub[mxN];
int f[mxN], invf[mxN];
bool cmp1(int a, int b)
{
    return sub[a]<sub[b];
}
void dfs1(int now, int pre)
{
    //printf("now=%d\n", now);
    sub[now]=1;
    msub[now]=-1;
    for(int nxt : v[now])
    {
        if(Chk[nxt] || nxt==pre)    continue;
        dfs1(nxt, now);
        sub[now]+=sub[nxt];
        if(msub[now]==-1)   msub[now]=nxt;
        else if(sub[msub[now]]<sub[nxt])   msub[now]=nxt;
    }
}
void dfs2(int now, int pre)
{
    //printf("2now=%d\n", now);
    sub[now]=1;
    for(int nxt : v[now])
    {
        if(Chk[nxt] || nxt==pre)    continue;
        dfs2(nxt, now);
        sub[now]+=sub[nxt];
    }
}
void Solve(int N) {
    for(int i=0;i<N;i++)    f[i]=i;
    random_shuffle(f, f+N);
    for(int i=0;i<N;i++)    invf[f[i]]=i;
    v[0].push_back(1);
    v[1].push_back(0);
    for(int i=2;i<N;i++)
    {
        if(used[i]) continue;
        int root=1;
        for(int j=0;j<N;j++)    Chk[j]=false;
        while(true)
        {
            dfs1(root, -1);
            int cent=root;
            while(msub[cent]!=-1 && sub[msub[cent]]*2>sub[cent])   cent=msub[cent];
            dfs2(cent, -1);
            //printf("cent=%d\n", cent);
            //for(int j=0;j<i;j++)    printf("Chk[%d]=%d\n", j, Chk[j]);
            /*for(int j=0;j<i;j++)
            {
                printf("%d: ", j);
                for(int nxt : g[j]) printf("%d ", nxt);
                printf("\n");
            }*/
            g[cent].clear();
            for(int nxt : v[cent])  if(!Chk[nxt])   g[cent].push_back(nxt);
            sort(g[cent].begin(), g[cent].end(), cmp1);
            if(g[cent].empty())
            {
                //printf("here");
                v[cent].push_back(i);
                v[i].push_back(cent);
                break;
            }
            bool par=true;
            bool flag=false;
            for(int j=0;j<g[cent].size();j++)
            {
                int nxt=g[cent][j];
                int res=invf[Query(f[cent], f[nxt], f[i])];
                if(res!=cent)
                {
                    par=false;
                    if(res==i)
                    {
                        //printf("s1");
                        for(int k=0;k<v[cent].size();k++)
                        {
                            if(v[cent][k]==nxt)
                            {
                                v[cent][k]=i;
                                break;
                            }
                        }
                        for(int k=0;k<v[nxt].size();k++)
                        {
                            if(v[nxt][k]==cent)
                            {
                                v[nxt][k]=i;
                                break;
                            }
                        }
                        v[i].push_back(cent);
                        v[i].push_back(nxt);
                        flag=true;
                    }
                    else if(res==nxt)
                    {
                        //printf("s2");
                        root=nxt;
                        Chk[cent]=true;
                        //assert(cent!=nxt);
                    }
                    else
                    {
                        //printf("s3");
                        for(int k=0;k<v[cent].size();k++)    {if(v[cent][k]==nxt) {v[cent][k]=res;   break;}}
                        for(int k=0;k<v[nxt].size();k++)    {if(v[nxt][k]==cent) {v[nxt][k]=res;    break;}}
                        v[res].push_back(cent);
                        v[res].push_back(nxt);
                        v[i].push_back(res);
                        v[res].push_back(i);
                        used[res]=true;
                        flag=true;
                    }
                    break;
                }
            }
            if(flag)    break;
            if(par)
            {
                v[cent].push_back(i);
                v[i].push_back(cent);
                break;
            }
        }
    }
    for(int i=0;i<N;i++)
    {
        for(int nxt : v[i])
        {
            if(f[nxt]>f[i]) Bridge(f[i], f[nxt]);
        }
    }
}

Compilation message (stderr)

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int j=0;j<g[cent].size();j++)
      |                         ~^~~~~~~~~~~~~~~
meetings.cpp:89:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                         for(int k=0;k<v[cent].size();k++)
      |                                     ~^~~~~~~~~~~~~~~
meetings.cpp:97:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                         for(int k=0;k<v[nxt].size();k++)
      |                                     ~^~~~~~~~~~~~~~
meetings.cpp:119:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |                         for(int k=0;k<v[cent].size();k++)    {if(v[cent][k]==nxt) {v[cent][k]=res;   break;}}
      |                                     ~^~~~~~~~~~~~~~~
meetings.cpp:120:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                         for(int k=0;k<v[nxt].size();k++)    {if(v[nxt][k]==cent) {v[nxt][k]=res;    break;}}
      |                                     ~^~~~~~~~~~~~~~

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