oj.uz

Submission #1118703

# Submission time Handle Problem Language Result Execution time Memory
1118703 2024-11-26T02:56:32 Z vjudge1 Izlet (COI19_izlet) C++14
100 / 100
 735 ms 83484 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 525 ms 62284 KB Output is correct
3 Correct 581 ms 62356 KB Output is correct
4 Correct 573 ms 61776 KB Output is correct
5 Correct 544 ms 62064 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 62296 KB Output is correct
2 Correct 557 ms 62028 KB Output is correct
3 Correct 686 ms 82800 KB Output is correct
4 Correct 735 ms 83484 KB Output is correct
5 Correct 575 ms 61892 KB Output is correct
6 Correct 517 ms 68948 KB Output is correct
7 Correct 452 ms 58884 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 525 ms 62284 KB Output is correct
3 Correct 581 ms 62356 KB Output is correct
4 Correct 573 ms 61776 KB Output is correct
5 Correct 544 ms 62064 KB Output is correct
6 Correct 487 ms 62296 KB Output is correct
7 Correct 557 ms 62028 KB Output is correct
8 Correct 686 ms 82800 KB Output is correct
9 Correct 735 ms 83484 KB Output is correct
10 Correct 575 ms 61892 KB Output is correct
11 Correct 517 ms 68948 KB Output is correct
12 Correct 452 ms 58884 KB Output is correct
13 Correct 529 ms 63308 KB Output is correct
14 Correct 580 ms 70232 KB Output is correct
15 Correct 504 ms 61672 KB Output is correct
16 Correct 701 ms 66124 KB Output is correct
17 Correct 632 ms 68264 KB Output is correct
18 Correct 617 ms 62440 KB Output is correct
19 Correct 582 ms 62252 KB Output is correct
20 Correct 600 ms 62004 KB Output is correct
21 Correct 508 ms 62820 KB Output is correct
22 Correct 536 ms 62540 KB Output is correct
23 Correct 622 ms 62924 KB Output is correct
24 Correct 580 ms 69276 KB Output is correct
25 Correct 641 ms 61888 KB Output is correct