QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153403 | #6329. Colorful Graph | aesthetic | WA | 2ms | 3636kb | C++14 | 5.9kb | 2023-08-30 00:25:34 | 2023-08-30 00:25:35 |
Judging History
answer
#include "bits/stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
// #define int long long
#define dbg_loc() cerr << __PRETTY_FUNCTION__ << " : " << __LINE__ << "\n"
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p){
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T_container,typename T=typename enable_if<!is_same<T_container,string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v){
os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}';
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){
cerr << ' ' << H;
dbg_out(T...);
}
#define LOCAL
#define LOCAL
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
///CUIDADO COM MAXN
#define N 7001 // 1E6
struct SCC{
vector< vi> g , comps;
vi val, z, cont, comp;
int Time =0, ncomps= 0 , n;
SCC(vector<vi> g, int n ):n(n) , g(g) , val(n+1,0), comp(n+1, -1) {}
int dfs(int j){
int low = val[j] = ++Time , x ; z.push_back(j);
trav(e, g[j]) if(comp[e] < 0)
low = min(low , val[e] ?: dfs(e));
if(low == val[j]){
do{
x = z.back() ; z.pop_back();
comp[x] = ncomps;
cont.push_back(x);
} while(x != j);
comps.push_back(cont) , cont.clear();
ncomps++;
}
return val[j] = low;
}
void scc(){
val.assign(n+1,0); comp.assign(n+1,-1);
Time = ncomps = 0 ;
rep(i,1,n+1) if(comp[i] < 0 ) dfs(i);
}
vector<vi> DAG(){// sem arestas repetidas
vector<vi> dag(n+1);val.assign(n+1,-1);
for(int i=0;i<ncomps;i++){
for(auto v : comps[i]){
for(auto to : g[v]){
if(val[comp[to]]==-1 && comp[to]!=i){
val[comp[to]]=1;
dag[i].pb(comp[to]);
}
}
}
for(auto v : comps[i])
for(auto to : g[v])
val[comp[to]]=-1;
}
return dag;
}
int repre(int c){
// representante da componente c (c < ncomps):
return comps[c][0];
}
};
int n,m;
vector<vi> grafo;
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool sameSet(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
return true;
}
};
struct Dinic {
struct Edge {
int to, rev;
ll c, oc;
ll flow() { return max(oc - c, 0LL); } // if you need flows
};
vi lvl, ptr, q;
vector<vector<Edge>> adj;
Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
void addEdge(int a, int b, ll c, int rcap = 0) {
adj[a].push_back({b, sz(adj[b]), c, c});
adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
}
ll dfs(int v, int t, ll f) {
if (v == t || !f) return f;
for (int& i = ptr[v]; i < sz(adj[v]); i++) {
Edge& e = adj[v][i];
if (lvl[e.to] == lvl[v] + 1)
if (ll p = dfs(e.to, t, min(f, e.c))) {
e.c -= p, adj[e.to][e.rev].c += p;
return p;
}
}
return 0;
}
ll calc(int s, int t) {
ll flow = 0; q[0] = s;
rep(L,0,31) do { // 'int L=30' maybe faster for random data
lvl = ptr = vi(sz(q));
int qi = 0, qe = lvl[s] = 1;
while (qi < qe && !lvl[t]) {
int v = q[qi++];
trav(e, adj[v])
if (!lvl[e.to] && e.c >> (30 - L))
q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
}
while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
} while (lvl[t]);
return flow;
}
bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
grafo.resize(n+1);
for(int i =1,a,b; i <= m; i++){
cin>>a>>b;
grafo[a].pb(b);
}
SCC T = SCC(grafo,n);
T.scc();
auto dag = T.DAG();
UF cu(n+1);
vi btoa(n + 1, -1), cor(n+1,-1);
Dinic dinic(2*T.ncomps + 10);
int src = 0, snk = 2*T.ncomps + 8;
for(int i = 0; i < T.ncomps; i++){
// dbg(i, T.comps[i]);
dinic.addEdge(src, i+1, 1);
dinic.addEdge(T.ncomps + (i+1), snk, 1);
dinic.addEdge(T.ncomps + (i+1), i+1, 1e7);
for(auto j: dag[i]){
dinic.addEdge(i+1,T.ncomps + (j+1), 1e7);
}
}
cout<<dinic.calc(src, snk)<<"\n";
for(int i = 1; i <= T.ncomps; i++){
for(int j = 0 ;j < sz(dinic.adj[i]); j++)
if(dinic.adj[i][j].to > T.ncomps and dinic.adj[i][j].c < (int)(1e7)){
// dbg("join", i-1, dinic.adj[i][j].to-1-T.ncomps);
cu.join(i-1, dinic.adj[i][j].to - 1 - T.ncomps);
}
}
int t=0;
for(int i = 0; i <= n; i++){
int pai = cu.find(i);
// dbg(i,pai);
if(cor[pai] == -1) cor[pai] = ++t;
}
for(int i = 1; i <= n; i++){
int cc = cor[ cu.find(T.comp[i]) ];
cout<<cc<<" \n"[i==n];
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3636kb
input:
5 5 1 4 2 3 1 3 2 5 5 1
output:
3 1 2 2 1 1
result:
wrong answer Integer 3 violates the range [1, 2]