Submission #234863

#	Time	Username	Problem	Language	Result	Execution time	Memory
234863		aggu_01000101	Izlet (COI19_izlet)	C++14	100 / 100	817 ms	89768 KiB

izlet

#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
using namespace std;
const int N = 3005;
int n;
int dist[N][N];
int root[N];
int sz[N];
bool vis[N];
int freq[N];
int col[N];
int curr = 1;
int tf = 0;
vector<int> adj[N];
int findroot(int i){
    if(i!=root[i]) root[i] = findroot(root[i]);
    return root[i];
}
void MERGE(int i, int j){
    int r1 = findroot(i);
    int r2 = findroot(j);
    if(r1==r2) return;
    if(sz[r1]>sz[r2]) swap(r1, r2);
    adj[j].push_back(i);
    adj[i].push_back(j);
    root[r1] = r2;
    sz[r2]+=sz[r1];
}
bool dfs1(int i, int p, int prevdist){
    if(i<=0) return false;
    if(!vis[i]) return false;
    if(freq[col[i]]==0 && prevdist==dist[tf][i]){
        col[tf] = col[i];
        return true;
    }
    bool tr = false;
    freq[col[i]]++;
    for(int j: adj[i]){
        if(j==p) continue;
        tr = tr || dfs1(j, i, dist[tf][i]);
    }
    freq[col[i]]--;
    return tr;
}
int dfs(int i, int p){
    tf = i;
    for(int k = 0;k<=n;k++){
        freq[k] = 0;
    }
    bool setnew = false;
    for(int j: adj[i]){
        setnew = setnew || dfs1(j, i, 1);
    }
    if(!setnew){
        col[i] = curr++;
    }
    vis[i] = true;
    for(int j: adj[i]){
        if(j==p) continue;
        dfs(j, i);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int type;
    cin>>type;
    cin>>n;
    for(int i = 1;i<=n;i++){
        root[i] = i;
        sz[i] = 1;
        vis[i] = false;
        for(int j = 1;j<=n;j++){
            cin>>dist[i][j];
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(dist[i][j]==1) MERGE(i, j);
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(dist[i][j]==2) MERGE(i, j);
        }
    }
    dfs(1, 0);
    for(int i = 1;i<=n;i++){
        cout<<col[i]<<" ";
    }
    cout<<endl;
    for(int i = 1;i<=n;i++){
        for(int j: adj[i]){
            if(j>i) cout<<i<<" "<<j<<endl;
        }
    }
    return 0;
}
/*
3
5
1 2 2 2 3
2 1 3 3 2
2 3 1 3 4
2 3 3 1 3
3 2 4 3 1
 */

/*
 2
 4
 1 2 3 3

 */

Compilation message (stderr)

izlet.cpp: In function 'long long int dfs(long long int, long long int)':
izlet.cpp:66:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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