Submission #144276

#	Time	Username	Problem	Language	Result	Execution time	Memory
144276		Abelyan	Izlet (COI19_izlet)	C++17	100 / 100	894 ms	83576 KiB

izlet

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=3e3+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

int qan[N][N],par[N],ans[N];
bool col[N],anc[N];
vector<int> g[N],tree[N];

int get(int v){
    if (par[v]==v)return v;
    return par[v]=get(par[v]);
}

void unite(int a,int b){
    a=get(a);
    b=get(b);
    if (a!=b){
        if (b>a)swap(a,b);
        par[a]=b;
    }
}

int cnt=1;

int getcol(int v,int sk,int pr=-1){
    //cout<<"hey "<<v<<" "<<sk<<" "<<qan[sk][pr]<<" "<<qan[sk][v]<<" "<<pr<<endl;
    if (pr!=-1 && !col[ans[v]]){
        col[ans[v]]=true;
        if (qan[sk][pr]==qan[sk][v])return ans[v];
    }
    //cout<<1<<endl;
    trav(to,tree[v])if (to!=pr && ans[to]){

        int stac=getcol(to,sk,v);
        if (stac)return stac;
    }
    return 0;
}
vector<pir> kox;

int n;
void dfs(int v,int pr=-1){
    //cout<<"mta "<<v<<endl;
    if (pr!=-1){
        kox.ad({v,pr});
        tree[pr].ad(v);
        tree[v].ad(pr);
    }
    anc[v]=true;
    trav(to,g[v])if (!anc[to])dfs(to,v);

}

void dfs2(int v,int pr=-1){
    //cout<<v<<endl;
    ans[v]=getcol(v,v);
    if (ans[v]==0)ans[v]=cnt++;
    FORT(i,1,n)col[i]=false;
    trav(to,tree[v])if(to!=pr)dfs2(to,v);
    //cout<<v<<endl;
}

int main(){
    fastio;
    srng;
    int tp;
    cin>>tp;
    cin>>n;
    FORT(i,1,n)par[i]=i;
    FORT(i,1,n){
        FORT(j,1,n){
            cin>>qan[i][j];
            if (qan[i][j]==1)unite(i,j);
        }
    }
    FORT(i,1,n){
        FORT(j,1,n){
            int a=get(i),b=get(j);
            if (qan[i][j]==2){
                g[a].ad(b);
            }
        }
    }
    //cout<<1<<endl;
    dfs(1);
    dfs2(1);
    FORT(i,1,n)cout<<ans[get(i)]<<" ";
    cout<<endl;
    FORT(i,1,n){
        if (i!=get(i))
            cout<<i<<" "<<get(i)<<endl;
    }
    trav(tv,kox)cout<<tv.fr<<" "<<tv.sc<<endl;
    return 0;
}

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