oj.uz

Submission #467559

# Submission time Handle Problem Language Result Execution time Memory
467559 2021-08-23T15:54:07 Z couplefire Izlet (COI19_izlet) C++17
100 / 100
 847 ms 74772 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 675 ms 53700 KB Output is correct
3 Correct 671 ms 53444 KB Output is correct
4 Correct 702 ms 53320 KB Output is correct
5 Correct 672 ms 53248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 53520 KB Output is correct
2 Correct 674 ms 53468 KB Output is correct
3 Correct 827 ms 74036 KB Output is correct
4 Correct 847 ms 74772 KB Output is correct
5 Correct 654 ms 53368 KB Output is correct
6 Correct 714 ms 60484 KB Output is correct
7 Correct 519 ms 49260 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 675 ms 53700 KB Output is correct
3 Correct 671 ms 53444 KB Output is correct
4 Correct 702 ms 53320 KB Output is correct
5 Correct 672 ms 53248 KB Output is correct
6 Correct 657 ms 53520 KB Output is correct
7 Correct 674 ms 53468 KB Output is correct
8 Correct 827 ms 74036 KB Output is correct
9 Correct 847 ms 74772 KB Output is correct
10 Correct 654 ms 53368 KB Output is correct
11 Correct 714 ms 60484 KB Output is correct
12 Correct 519 ms 49260 KB Output is correct
13 Correct 667 ms 54408 KB Output is correct
14 Correct 808 ms 61256 KB Output is correct
15 Correct 671 ms 53548 KB Output is correct
16 Correct 719 ms 57904 KB Output is correct
17 Correct 732 ms 59908 KB Output is correct
18 Correct 673 ms 53360 KB Output is correct
19 Correct 707 ms 53444 KB Output is correct
20 Correct 667 ms 53520 KB Output is correct
21 Correct 692 ms 54052 KB Output is correct
22 Correct 680 ms 53916 KB Output is correct
23 Correct 659 ms 54212 KB Output is correct
24 Correct 747 ms 60468 KB Output is correct
25 Correct 670 ms 53564 KB Output is correct