Submission #167292

#	Time	Username	Problem	Language	Result	Execution time	Memory
167292		Atill83	Izlet (COI19_izlet)	C++14	0 / 100	2081 ms	266652 KiB

izlet

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int c[MAXN][MAXN];
vector<pii> edges;
int renk[MAXN];
int par[MAXN];
int path[MAXN][MAXN];
map<int, bool> mp[MAXN];
vector<pii> say[MAXN];
vector<int> adj[MAXN];
int find_set(int a){
    if(par[a] == a){
        return a;
    }
    return par[a] = find_set(par[a]);
}

void merge_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    par[b] = a;
}
bool visited[MAXN][MAXN];
int mes[MAXN][MAXN];

void dd(int a, int bas, int par = -1){
    for(int i: adj[a]){
        if(i != par){
            mes[bas][i] = mes[bas][a] + 1;
            dd(i, bas, a);
        }
    }
}


void dfs(int a, int b, int para, int parb){
    //cout<<a<<" "<<b<<" "<<para<<" "<<parb<<endl;
    //a = find_set(a);
    //b = find_set(b);
    if(a != b){
        if(para != -1 && c[a][b] == c[para][b] && renk[a] != renk[para]){
            //cout<<"ali"<<endl;
            renk[a] = renk[b];
        }else if(parb != -1 && c[a][b] == c[a][parb] && renk[b] != renk[parb]){
            renk[a] = renk[b];
            //cout<<"veli"<<endl;
        }
    }
    //cout<<renk[a]<<" "<<renk[b]<<endl;
    for(int j: adj[a]){
            if(j == para) continue;
            if(!visited[j][b] && mes[a][b] < mes[j][b]){
                visited[j][b] = visited[b][j] = 1;
                dfs(j, b, a, -1);
            }
            if(!visited[j][j]){
                visited[j][j] = 1;
                dfs(j, j, -1, -1);
            }
        }
    for(int j: adj[b]){
        if(j == parb) continue;
        if(!visited[a][j] && mes[a][b] < mes[a][j]){
            visited[a][j] = visited[j][a] = 1;
            dfs(a, j, -1, b);
        }
        if(!visited[j][j]){
            visited[j][j] = 1;
            dfs(j, j, -1, -1);
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif
    int a;
    cin>>a;
    cin>>n;
    for(int i = 1; i <= n; i++){
        renk[i] = i;
        par[i] = i;
        for(int j = 1; j <= n; j++){
            cin>>c[i][j];
            if(i > j){
                say[c[i][j]].push_back({i, j});
                if(c[i][j] == 2){
                    mp[i][j] = 1;
                    mp[j][i] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= 2; i++){
        for(pii j: say[i]){
            int a = j.ff, b = j.ss;
            if(find_set(a) == find_set(b)) continue;
            merge_set(a, b);
            edges.push_back({a, b});
            adj[a].push_back(b);
            adj[b].push_back(a);
            
        }
    }
    for(int i = 1; i <= n; i++){
        dd(i, i);
    }
    visited[1][1] = 1;
    path[1][1] = 1;
    dfs(1, 1, - 1, -1);

    for(int i = 1; i <= n; i++){
        cout<<renk[i]<<" ";
    }
    cout<<endl;
    for(pii i: edges)
        cout<<i.ss<<" "<<i.ff<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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