oj.uz

Submission #559404

# Submission time Handle Problem Language Result Execution time Memory
559404 2022-05-09T17:43:32 Z leaked Izlet (COI19_izlet) C++17
100 / 100
 723 ms 73556 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=3e3+1;
//int c[N][N];
struct dsu{
    int p[N];
    dsu(){
        iota(p,p+N,0);
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
    bool mg(int a,int b,int need=0){
        a=get(a),b=get(b);
        if(a==b) return 0;
//        if(need){
//            for(int i=0;i<n;i++)
//                assert(c[a][i]==c[b][i]);
//        }
        p[a]=b;
        return 1;
    }
}ds;
vec<int> g[N];
int x[N][N];
int clr[N],cnt;
bool can(int a,int b,int v,int p){
    if(x[a][v]==x[a][p]){
        clr[v]=clr[a];
//        cout<<"W "<<clr[v]<<' '<<clr[a]<<' '<<v<<' '<<a<<endl;
//        cout<<"W "<<a<<' '<<v<<' '<<a<<' '<<p<<endl;
        return 1;
    }
    for(auto &z : g[a]){
        if(z!=b && clr[z])
            if(can(z,a,v,p)) return 1;
    }
    return 0;
}
void dfs(int v,int p){
    if(v==p || !can(p,v,v,p))
        clr[v]=++cnt;
//    cout<<"
    for(auto &z : g[v]){
        if(z!=p)
            dfs(z,v);
    }
}

int n;

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    ifstream cin("input.txt");
    int t;
    cin>>t>>n;
    vec<pii> e;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>x[i][j];
//        for(int j=0;j<n;j++){
//            if(c[i][j]==1)
//                ds.mg(i,j,1);
//        }
    }
    for(int t=1;t<=2;t++){
        for(int v=0;v<n;v++){
            for(int u=0;u<n;u++){
                if(x[v][u]==t && ds.mg(v,u))
                    e.pb({v,u}),g[v].pb(u),g[u].pb(v);
            }
        }
    }
    dfs(0,0);
    for(int i=0;i<n;i++){
        cout<<clr[i]<<' ';
    }
    cout<<'\n';
    for(auto &z : e)
        cout<<z.f+1<<' '<<z.s+1<<endl;
    return 0;
}
/*

*/

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 545 ms 35772 KB Output is correct
3 Correct 585 ms 35816 KB Output is correct
4 Correct 560 ms 35760 KB Output is correct
5 Correct 515 ms 35676 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 35904 KB Output is correct
2 Correct 605 ms 53476 KB Output is correct
3 Correct 681 ms 73556 KB Output is correct
4 Correct 723 ms 70468 KB Output is correct
5 Correct 502 ms 53352 KB Output is correct
6 Correct 521 ms 60376 KB Output is correct
7 Correct 405 ms 49244 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 545 ms 35772 KB Output is correct
3 Correct 585 ms 35816 KB Output is correct
4 Correct 560 ms 35760 KB Output is correct
5 Correct 515 ms 35676 KB Output is correct
6 Correct 506 ms 35904 KB Output is correct
7 Correct 605 ms 53476 KB Output is correct
8 Correct 681 ms 73556 KB Output is correct
9 Correct 723 ms 70468 KB Output is correct
10 Correct 502 ms 53352 KB Output is correct
11 Correct 521 ms 60376 KB Output is correct
12 Correct 405 ms 49244 KB Output is correct
13 Correct 553 ms 54220 KB Output is correct
14 Correct 663 ms 61220 KB Output is correct
15 Correct 518 ms 53404 KB Output is correct
16 Correct 575 ms 57924 KB Output is correct
17 Correct 600 ms 59732 KB Output is correct
18 Correct 477 ms 53296 KB Output is correct
19 Correct 576 ms 53476 KB Output is correct
20 Correct 539 ms 53248 KB Output is correct
21 Correct 522 ms 54004 KB Output is correct
22 Correct 550 ms 53748 KB Output is correct
23 Correct 514 ms 54160 KB Output is correct
24 Correct 588 ms 60492 KB Output is correct
25 Correct 521 ms 53472 KB Output is correct