Submission #467559

#	Time	Username	Problem	Language	Result	Execution time	Memory
467559		couplefire	Izlet (COI19_izlet)	C++17	100 / 100	847 ms	74772 KiB

izlet

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

const int N = 3005;

int _, n, grid[N][N], fa[N], ans[N], top;
vector<int> adj[N]; bool vis[N];
vector<array<int, 2>> edges;

int find(int v){return v==fa[v]?v:fa[v]=find(fa[v]);}

void unite(int u, int v){
    int tu = find(u), tv = find(v);
    if(tu==tv) return;
    fa[tu] = tv;
    adj[u].push_back(v);
    adj[v].push_back(u);
    edges.push_back({u, v});
}

bool dfs2(int v, int p, int a, int b){
    if(grid[a][v]==grid[b][v]){ans[a] = ans[v]; return 1;}
    for(auto u : adj[v])
        if(vis[u] && u!=p)
            if(dfs2(u, v, a, b)) return 1;
    return 0;
}

void dfs1(int v, int p){
    vis[v] = 1;
    if(p==-1 || !dfs2(p, v, v, p)) ans[v] = top++;
    for(auto u : adj[v])
        if(u!=p) dfs1(u, v);
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> _ >> n;
    for(int i = 0; i<n; ++i)
        for(int j = 0; j<n; ++j)
            cin >> grid[i][j];
    iota(fa, fa+n, 0);
    for(int val = 1; val<=2; ++val)
        for(int i = 0; i<n; ++i)
            for(int j = i+1; j<n; ++j)
                if(grid[i][j]==val) unite(i, j);
    dfs1(0, -1);
    for(int i = 0; i<n; ++i)
        cout << ans[i]+1 << ' ';
    cout << '\n';
    for(auto [a, b] : edges)
        cout << a+1 << ' ' << b+1 << '\n';
}

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