QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473631 | #6833. My University Is Better Than Yours | prime-ideal | RE | 0ms | 0kb | C++20 | 1.8kb | 2024-07-12 11:50:26 | 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 2 1 2 3 4 1 3 2 4