結果

問題 No.2987 Colorful University of Tree
ユーザー 可爱妹妹
提出日時 2025-05-24 18:30:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 8,756 bytes
コンパイル時間 3,007 ms
コンパイル使用メモリ 213,236 KB
実行使用メモリ 41,024 KB
最終ジャッジ日時 2025-05-24 18:30:40
合計ジャッジ時間 13,437 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 33 RE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:9: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |    scanf("%d",&n);
      |    ~~~~~^~~~~~~~~
main.cpp:53:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |       scanf("%d",&k);
      |       ~~~~~^~~~~~~~~
main.cpp:57:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |          scanf("%d",&x);
      |          ~~~~~^~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
int len[200005];
vector<pair<int,int> > D;
int sum[200005];
vector<int> need[200005];
vector<int> E[200005];
vector<int> col[200005];
int qeta[400005];
int belone[200005];
int stb[200005];
vector<pair<int,int> > G[200005];
vector<int> self[200005];
int chk[200005];
vector<int> whe[200005];
bool check(int Q){//
   int tim=1;
   while(tim--){
      for(int i=1;i<=Q;i++)sum[i]=0,need[i].clear();
      for(int i=1;i<D.size();i++)swap(D[i],D[rand()%i]);
      for(int i=D.size()-1;i>=0;i--){
         bool flg=false;//
         for(int j=1;j<=Q;j++){
            if(sum[j]+D[i].first<=Q){
               sum[j]+=D[i].first;
               flg=true;//
               need[j].push_back(D[i].second);
               belone[D[i].second]=j;
               break;
            }
         }
         if(!flg)break;//
         if(!i)return true;
      }
   }
   return false;
}
bool cmp(int a,int b){
   return G[a].size()>G[b].size();
}
int nxt[200005];
int find(int x){return nxt[x]==x?x:nxt[x]=find(nxt[x]);}
int main(){
   srand(time(0));
   // freopen("city.in","r",stdin);
   // freopen("city.out","w",stdout);
   scanf("%d",&n);
   ans=ceil(sqrt(2*(n-1)));
   for(int i=1;i<=n;i++){
      int k;
      scanf("%d",&k);
      len[i]=k;
      int x;
      for(int j=1;j<=k;j++){
         scanf("%d",&x);
         whe[i].push_back(x+E[x].size()*n);
         E[x].push_back(i);
      }
      // printf("%lu\n",whe[i].size());
      // return 0;
      ans=max(ans,k);
      D.push_back(make_pair(k,i));
   }
   sort(D.begin(),D.end());
   while(!check(ans))ans++;
   printf("%d\n",ans);
   // for(int i=1;i<=n;i++){
   //    printf("%d ",1);
   //    for(int j=1;j<=len[i];j++)printf("%d ",1);
   //    puts("");
   // }
   for(int i=1;i<n;i++){//如果他自己连自己，考虑预先分配颜色给他就好了
      int u=E[i][0];
      int v=E[i][1];
      if(belone[u]==belone[v]){
         self[belone[u]].push_back(i);
         continue;
      }
      // printf("id=%d (%d,%d) %d -> %d\n",i,u,v,belone[u],belone[v]);
      G[belone[u]].push_back(make_pair(belone[v],i));
      G[belone[v]].push_back(make_pair(belone[u],n+i));
   }
   vector<int> id;
   for(int i=1;i<=ans;i++)id.push_back(i);
   int tim=1;
   while(tim--){
      sort(id.begin(),id.end(),cmp);
   // return 0;
      //考虑对于每个色块，枚举一下邻接边，然后再随机枚举一个颜色，把他分配给他没出现的地方
      //考虑每次选择的颜色，要求出现次数最多好了，然后分配完之后他的位置就可以随便占真是太方便了
      //对于相等的就随机选
      //不对，这个意思不就是，不管怎么样，都能分配出来，但是还是得按照度数排序，因为极端情况有可能需要用Q+1次，大概是这样
      //然后对于每个点其实也不一定要很严格说度数怎么怎么分配，只要一个点往外分配，他自己的位置就一定会空出来，所以就没有问题
      //我不应该这么早就定下那些自己指向自己的边应该怎么样选择。
      for(int i=0;i<id.size();i++){
         int now=id[i];
         // cerr<<now<<'\n';
         // printf("now=%d\n",now);
         // printf("i=%d now=%d\n",i,now);
         vector<int> D;
         // for(int j=1;j<=ans;j++){//对于一个颜色，只要对外有一点点就统计好了
         //    chk[j]=false;
         // }
         vector<int> ruozhi;
         for(int j=0;j<G[now].size();j++){
            int v=G[now][j].first;
            int id=G[now][j].second;
            if(id>n){
               if(qeta[id-n]){
                  ruozhi.push_back(qeta[id-n]);
                  chk[qeta[id-n]]=now;
               }
            }
            else{
               if(qeta[id+n]){
                  ruozhi.push_back(qeta[id+n]);
                  chk[qeta[id+n]]=now;
               }
            }
         }
         sort(ruozhi.begin(),ruozhi.end());
         if(ruozhi.size())D.push_back(ruozhi[0]);
         for(int i=1;i<ruozhi.size();i++){
            if(ruozhi[i] xor ruozhi[i-1])D.push_back(ruozhi[i]);
         }
         // for(int j=1;j<=ans;j++){
         //    if(chk[j]){
         //       D.push_back(j);
         //    }
         // }
         for(int j=1;j<D.size();j++){
            swap(D[j],D[rand()%j]);
         }
         // printf("sizD=%lu sizG=%lu\n",D.size(),G[now].size());
         // if(D.size())return 0;
         // puts("CLEAR!!");

         for(int k=0;k<=G[now].size();k++)nxt[k]=k;
         for(int j=0;j<D.size();j++){
            // return 0;
            int ncol=D[j];
            // printf("ncol=%d\n",ncol);
            int k=find(0);
            while(k<G[now].size()){
               int v=G[now][k].first;
               int id=G[now][k].second;
               if(qeta[id]){
                  k=find(k+1);
                  continue;
               }
               // printf("k=%d id=%d\n",k,id);
               if(id>n){
                  if(qeta[id-n]==ncol){
                     k=find(k+1);
                     continue;
                  }
                  qeta[id]=ncol;
                  nxt[k]=k+1;
                  break;
               }
               else{
                  if(qeta[id+n]==ncol){
                     k=find(k+1);
                     continue;
                  }
                  qeta[id]=ncol;
                  nxt[k]=k+1;
                  break;
               }
               // if(k+1==G[now].size()){
               //    puts("error");
               // }
            }
         }
         // if(i==0)return 0;
         D.clear();
         int all=2*self[now].size();
         for(int j=0;j<G[now].size();j++){
            int v=G[now][j].first;
            int id=G[now][j].second;
            if(qeta[id])continue;
            all++;
         }
         // printf("i=%d\n",i);
         // puts("clear!");
         for(int j=1;j<=ans&&D.size()<all;j++){
            if(chk[j] xor now){
               D.push_back(j);
            }
         }
         assert(D.size()==all);
         for(int j=1;j<D.size();j++){
            swap(D[j],D[rand()%j]);
         }
         // printf("siz=%lu sizG=%lu sizself=%lu\n",D.size(),G[now].size(),self[]);
         int stb=0;
         for(int j=0;j<G[now].size();j++){
            int v=G[now][j].first;
            int id=G[now][j].second;
            if(qeta[id])continue;
            qeta[id]=D[stb++];
         }
         for(int j=0;j<self[now].size();j++){
            int eid=self[now][j];
            qeta[eid]=D[stb++];
            assert(stb<D.size());
            qeta[n+eid]=D[stb++];
         }
         // puts("clear!");
         // if(now==45)return 0;
      }
      // puts("CLEAR!!");
      for(int i=1;i<=n;i++){
         // printf("i=%d siz=%lu\n",i,whe[i].size());
         printf("%d ",belone[i]);
         for(int j=0;j<whe[i].size();j++){
            // printf("%d\n",whe[i][j]);
            printf("%d ",qeta[whe[i][j]]);
         }
         // printf("i=%d\n",i);
         puts("");
      }
   }
   // puts("No Source!")
   //考虑这样都成功了！
   //现在要做的事情就是开始拆分，然后但是有问题就是，我要求一条边的两端给出的颜色不准相同
   //考虑先不管这个事情，暴力分配一下颜色
   //如果没有一条边链接两个一样的颜色那就很好了
   //否则的话考虑进行交换，我们先把色块弄出来，然后把色块之间的边集弄出来
   //考虑我先从一个色块开始搜索，直接对颜色进行标号
   //然后往相邻色块走。
   //当两个色块之间有多条边的时候可以轮换，我们把这样的边称为重边，重边随便给标号后就可以删除
   //这也太麻烦，考虑我直接搜，往下搜的时候每条边分配一个当前颜色块没选过的颜色，下面也这么往上给？
   //给边新建一个点，那么新图上的边的一条边的颜色必须相同，同时每个边点还要满足一个点不能有相同颜色的限制
   //考虑把缩点之后的图建出来，那么这样的话限制就变成了不准有两条共点的边取到同种颜色
   //长得有点像最大独立集。
   //考虑我先分配一个点的颜色，这样子持续增量构造
   //度数从大到小开始分配，然后每次随机分配颜色，这样子重复做100次
   //
   return 0;
}
/*
考虑相当于是把点分给 Q 个集合，使得每个集合的总度数不超过 Q，问最小的Q

极值不一定取得到，比较不权威

考虑我枚举一下这个Q，因为大概就是根号级别的，大不了多少，然后考虑怎么分能判断Q是否可行呢。

首先在根号n以上的点

尝试贪心一下，优先分大的

*/
0