Submission #1118703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118703		vjudge1	Izlet (COI19_izlet)	C++14	100 / 100	735 ms	83484 KiB

izlet

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

const int NV=3e3;

namespace ufs{
    int f[NV+5];
    void init(int n){
        for(int i=0;i<=n;++i) f[i]=i;
    }int fd(int x){
        return x==f[x]?x:f[x]=fd(f[x]);
    }
}

namespace xm{
    std::vector<int> G[NV+5];
    int a[NV+5][NV+5],col[NV+5];
    bool sam[NV+5][NV+5];

    int active,res,cnt[NV+5],colc;
    void getc(int x,int p,int s){
        //fprintf(stderr,"getc %d %d\n",x,p);
        active+=cnt[col[x]]++==0;
        if(res==-1&&active!=a[s][x]) res=col[x];
        for(int t:G[x]) if(col[t]&&t!=p){
            //fprintf(stderr,"%d->%d\n",x,t);
            getc(t,x,s);
        }
        active-=--cnt[col[x]]==0;
    }int chk(int x){
        memset(cnt,0,sizeof cnt);
        active=0;
        res=-1;
        //fprintf(stderr,"chk %d\n",x);
        getc(x,-1,x);
        return ~res?res:++colc;
    }void dfs(int x){
        col[x]=chk(x);
        for(int t:G[x]) if(!col[t]) dfs(t);
    }void _(){
        int N;

        scanf("%*d%d",&N);
        for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) scanf("%d",a[i]+j);
        ufs::init(N);
        for(int i=1;i<=N;++i) for(int j=i+1;j<=N;++j) if(a[i][j]==1){
            if(ufs::fd(i)==ufs::fd(j)) continue;
            G[ufs::fd(i)].push_back(ufs::fd(j));
            G[ufs::fd(j)].push_back(ufs::fd(i));
            //printf("merge %d %d\n",ufs::fd(j),ufs::fd(i));
            ufs::f[ufs::fd(i)]=ufs::fd(j);
        }
        std::vector<int> cen;
        for(int i=1;i<=N;++i) if(ufs::f[i]==i) cen.push_back(i);
        int M=cen.size();
        for(int i=0;i<M;++i) for(int j=i+1;j<M;++j){
            const int u=cen[i],v=cen[j];
            if(!(a[u][v]==2&&!sam[u][v])) continue;
            std::vector<int> l2{u,v};
            for(int k=j+1;k<M;++k){
                const int w=cen[k];
                if(a[u][w]==2&&a[v][w]==2)
                    l2.push_back(w);
            }
            const int l2s=l2.size();
            for(int a=0;a<l2s;++a) for(int b=0;b<l2s;++b)
                sam[l2[a]][l2[b]]=sam[l2[b]][l2[a]]=1;
            for(int a=1;a<l2s;++a){
                G[l2[0]].push_back(l2[a]);
                G[l2[a]].push_back(l2[0]);
            }
        }
        dfs(1);
        for(int i=1;i<=N;++i) printf("%d ",col[i]);
        puts("");
        for(int i=1;i<=N;++i) for(int t:G[i]) if(i<t) printf("%d %d\n",i,t);
    }
}

int main(){
    xm::_();
    return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'void xm::_()':
izlet.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%*d%d",&N);
      |         ~~~~~^~~~~~~~~~~~
izlet.cpp:55:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) scanf("%d",a[i]+j);
      |                                                     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57