Submission #369867

#	Time	Username	Problem	Language	Result	Execution time	Memory
369867		azberjibiou	Meetings (JOI19_meetings)	C++17	7 / 100	2 ms	620 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];
bool cmp1(int a, int b)
{
    return sub[a]>sub[b];
}
void dfs1(int now, int pre)
{
    //printf("now=%d\n", now);
    g[now].clear();
    sub[now]=1;
    for(int nxt : v[now])
    {
        if(Chk[nxt] || nxt==pre)    continue;
        dfs1(nxt, now);
        sub[now]+=sub[nxt];
        if(g[now].empty())  g[now].push_back(nxt);
        else if(sub[g[now][0]]<sub[nxt])    g[now][0]=nxt;
    }
}
void dfs2(int now, int pre)
{
    //printf("2now=%d\n", now);
    g[now].clear();
    sub[now]=1;
    for(int nxt : v[now])
    {
        if(Chk[nxt] || nxt==pre)    continue;
        dfs2(nxt, now);
        sub[now]+=sub[nxt];
        g[now].push_back(nxt);
    }
}
void Solve(int N) {
    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<i;j++)    Chk[j]=false;
        int cnt=0;
        while(true)
        {
            if(N>=10)   return;
            cnt++;
            if(cnt>=10)
            {
                return;
            }
            dfs1(root, -1);
            int cent=root;
            while(!g[cent].empty() && sub[g[cent][0]]*2>=sub[cent])   cent=g[cent][0];
            dfs2(cent, -1);
            if(g[cent].empty())
            {
                //printf("here");
                v[cent].push_back(i);
                v[i].push_back(cent);
                break;
            }
            bool par=true;
            bool flag=false;
            sort(g[cent].begin(), g[cent].end(), cmp1);
            for(int j=0;j<g[cent].size();j++)
            {
                int nxt=g[cent][j];
                int res=Query(cent, nxt, 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;
                        for(int k=0;k<v[nxt].size();k++)    if(v[nxt][k]==cent) v[nxt][k]=i;
                        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;
                        for(int k=0;k<v[nxt].size();k++)    if(v[nxt][k]==cent) v[nxt][k]=res;
                        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(nxt>i)   Bridge(i, nxt);
        }
    }
}

Compilation message (stderr)

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

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