QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473631#6833. My University Is Better Than Yoursprime-idealRE 0ms0kbC++201.8kb2024-07-12 11:50:262024-07-12 11:50:26

Judging History

你现在查看的是最新测评结果

  • [2024-07-12 11:50:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-12 11:50:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define RN return
#define forw(_,l,r) for(auto _=(l);_<(r);++_)
#define fors(_,r,l) for(auto _=(r);_>(l);--_)
// #define DEBUG if((cout<<"line:"<<__LINE__<<'\n'), 1)
#define DEBUG if(0)
// #define int ll
#define fastio cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);

void read(){}
template<typename T,typename...Types>
void read(T& x, Types&...args){
  x=0; char c=' '; bool sgn=0;
  while(isspace(c))c=getchar();
  if(c=='-')c=getchar(),sgn=1;
  while(isdigit(c))x=10*x+c-'0',c=getchar();
  if(sgn)x=-x;
  read(args...);
}
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int NUM=5e1+10;
vi adj[NUM]={},radj[NUM];
int d[NUM]={},sum[NUM]={};
char vis[NUM], grey=1, black=2;
int fa[NUM], low[NUM];
int find(int x){RN x==low[x]?x:low[x]=find(low[x]);}
void dfs(int x){
  vis[x]=grey;
  for(auto t: adj[x]){
    if(!vis[t])fa[t]=x,dfs(t);
    else if(vis[t=find(t)]==black){
      radj[t].push_back(x);continue;
    }else for(int s=x;s!=t;s=find(fa[s]))low[s]=t;
  } vis[x]=black;
}
int main()
{
  int n,m;read(n,m);
  forw(i,0,m){
    int a;read(a);
    forw(i,1,n){
      int b;read(b);adj[a].push_back(b);a=b;
    }
  }
  iota(low,low+n+1,0);
  forw(i,1,n+1)dfs(i);
  forw(i,1,n+1){
    if(find(i)==i){
      if(fa[i])radj[i].push_back(fa[i]);
      auto&v=radj[i];
      for(auto& x:v)x=find(x),x=(x==i?0:x);//!
      sort(v.begin(),v.end());
      v.resize(unique(v.begin(),v.end())-v.begin()-!(v.back()));//
      for(auto x:v)++d[x];
    }++sum[find(i)];
  }
  stack<int> stk;
  forw(i,1,n+1)if(find(i)==i&&d[i]==0)stk.push(i);
  while(!stk.empty()){
    int top=stk.top();stk.pop();
    for(auto x:radj[top]){
      --d[x],sum[x]+=sum[top];
      if(d[x]==0)stk.push(x);//!
    }
  }
  forw(i,1,n+1)cout<<sum[find(i)]-1<<' ';
  RN 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

4 2
1 2 3 4
1 3 2 4

output:


result: