Submission #559404

#	Time	Username	Problem	Language	Result	Execution time	Memory
559404		leaked	Izlet (COI19_izlet)	C++17	100 / 100	723 ms	73556 KiB

izlet

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=3e3+1;
//int c[N][N];
struct dsu{
    int p[N];
    dsu(){
        iota(p,p+N,0);
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
    bool mg(int a,int b,int need=0){
        a=get(a),b=get(b);
        if(a==b) return 0;
//        if(need){
//            for(int i=0;i<n;i++)
//                assert(c[a][i]==c[b][i]);
//        }
        p[a]=b;
        return 1;
    }
}ds;
vec<int> g[N];
int x[N][N];
int clr[N],cnt;
bool can(int a,int b,int v,int p){
    if(x[a][v]==x[a][p]){
        clr[v]=clr[a];
//        cout<<"W "<<clr[v]<<' '<<clr[a]<<' '<<v<<' '<<a<<endl;
//        cout<<"W "<<a<<' '<<v<<' '<<a<<' '<<p<<endl;
        return 1;
    }
    for(auto &z : g[a]){
        if(z!=b && clr[z])
            if(can(z,a,v,p)) return 1;
    }
    return 0;
}
void dfs(int v,int p){
    if(v==p || !can(p,v,v,p))
        clr[v]=++cnt;
//    cout<<"
    for(auto &z : g[v]){
        if(z!=p)
            dfs(z,v);
    }
}

int n;

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    ifstream cin("input.txt");
    int t;
    cin>>t>>n;
    vec<pii> e;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>x[i][j];
//        for(int j=0;j<n;j++){
//            if(c[i][j]==1)
//                ds.mg(i,j,1);
//        }
    }
    for(int t=1;t<=2;t++){
        for(int v=0;v<n;v++){
            for(int u=0;u<n;u++){
                if(x[v][u]==t && ds.mg(v,u))
                    e.pb({v,u}),g[v].pb(u),g[u].pb(v);
            }
        }
    }
    dfs(0,0);
    for(int i=0;i<n;i++){
        cout<<clr[i]<<' ';
    }
    cout<<'\n';
    for(auto &z : e)
        cout<<z.f+1<<' '<<z.s+1<<endl;
    return 0;
}
/*

*/

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57