oj.uz

Submission #234863

# Submission time Handle Problem Language Result Execution time Memory
234863 2020-05-26T06:00:54 Z aggu_01000101 Izlet (COI19_izlet) C++14
100 / 100
 817 ms 89768 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 633 ms 71292 KB Output is correct
3 Correct 592 ms 71160 KB Output is correct
4 Correct 597 ms 71160 KB Output is correct
5 Correct 596 ms 71164 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 71328 KB Output is correct
2 Correct 625 ms 71416 KB Output is correct
3 Correct 801 ms 73080 KB Output is correct
4 Correct 817 ms 80248 KB Output is correct
5 Correct 567 ms 71544 KB Output is correct
6 Correct 678 ms 76920 KB Output is correct
7 Correct 521 ms 79348 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 633 ms 71292 KB Output is correct
3 Correct 592 ms 71160 KB Output is correct
4 Correct 597 ms 71160 KB Output is correct
5 Correct 596 ms 71164 KB Output is correct
6 Correct 584 ms 71328 KB Output is correct
7 Correct 625 ms 71416 KB Output is correct
8 Correct 801 ms 73080 KB Output is correct
9 Correct 817 ms 80248 KB Output is correct
10 Correct 567 ms 71544 KB Output is correct
11 Correct 678 ms 76920 KB Output is correct
12 Correct 521 ms 79348 KB Output is correct
13 Correct 601 ms 89768 KB Output is correct
14 Correct 797 ms 76792 KB Output is correct
15 Correct 615 ms 72416 KB Output is correct
16 Correct 714 ms 76972 KB Output is correct
17 Correct 705 ms 76860 KB Output is correct
18 Correct 587 ms 88824 KB Output is correct
19 Correct 668 ms 88848 KB Output is correct
20 Correct 592 ms 88952 KB Output is correct
21 Correct 627 ms 89592 KB Output is correct
22 Correct 580 ms 72096 KB Output is correct
23 Correct 605 ms 89464 KB Output is correct
24 Correct 720 ms 76536 KB Output is correct
25 Correct 568 ms 72312 KB Output is correct