Submission #749823

#	Time	Username	Problem	Language	Result	Execution time	Memory
749823		Username4132	Izlet (COI19_izlet)	C++14	100 / 100	777 ms	74808 KiB

izlet

#include<iostream>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back

const int MAXN=3010;
int subtask, n, comInd, arr[MAXN][MAXN], com[MAXN], low[MAXN], tin[MAXN], color[MAXN], par[MAXN], lst[MAXN], tm, ch, cnt;
bool solved[MAXN][MAXN], vis[MAXN];
vector<int> els[MAXN], g[MAXN], st;

void dfs1(int v){
    com[v]=comInd;
    forn(to, n) if(arr[v][to]==1 && !com[to]) dfs1(to);
}

void dfs2(int v){
    tin[v]=low[v]=tm++;
    vis[v]=true;
    st.PB(v);
    forn(to, comInd) if(arr[v][els[to][0]]==2){
        if(vis[els[to][0]]) low[v]=min(low[v], tin[els[to][0]]);
        else{
            dfs2(els[to][0]);
            low[v]=min(low[v], low[els[to][0]]);
            if(v==els[0][0] || low[els[to][0]]>=tin[v]){
                while(!st.empty() && st.back()!=v){
                    g[st.back()].PB(v);
                    g[v].PB(st.back());
                    st.pop_back();
                }
            }
        }
    }
}

void dfs3(int v, int p){
    par[v]=p;
    for(int to:g[v]) if(color[to]!=n && to!=p){
        dfs3(to, v);
    }
    lst[color[v]]=v;
}

void dfs4(int v, int p){
    int col=-1;
    forn(i, n) lst[i]=-1;
    dfs3(v, v);
    forn(i, n) if(lst[i]!=-1 && arr[v][lst[i]]==arr[v][par[lst[i]]]) col=i;
    if(col==-1) col=cnt++;
    color[v]=col;    
    for(int to:g[v]) if(to!=p) dfs4(to, v);
}

int main(){
    scanf("%d", &subtask);
    scanf("%d", &n);
    forn(i, n) forn(j, n) scanf("%d", &arr[i][j]);
    forn(i, n) if(!com[i]) ++comInd, dfs1(i);
    forn(i, n) els[com[i]-1].PB(i);

    dfs2(els[0][0]);
    forn(i, comInd) forsn(j, 1, els[i].size()){
        g[els[i][0]].PB(els[i][j]);
        g[els[i][j]].PB(els[i][0]);
    }

    forn(i, n) color[i]=n;
    dfs4(0, 0);
    forn(i, n) printf("%d ", color[i]+1);
    printf("\n");
    forn(i, n) for(int j:g[i]) if(j>i) printf("%d %d\n", i+1, j+1);
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &subtask);
      |     ~~~~~^~~~~~~~~~~~~~~~
izlet.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
izlet.cpp:59:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     forn(i, n) forn(j, n) scanf("%d", &arr[i][j]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~

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