oj.uz

Submission #144276

# Submission time Handle Problem Language Result Execution time Memory
144276 2019-08-16T13:25:28 Z Abelyan Izlet (COI19_izlet) C++17
100 / 100
 894 ms 83576 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=3e3+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

int qan[N][N],par[N],ans[N];
bool col[N],anc[N];
vector<int> g[N],tree[N];

int get(int v){
    if (par[v]==v)return v;
    return par[v]=get(par[v]);
}

void unite(int a,int b){
    a=get(a);
    b=get(b);
    if (a!=b){
        if (b>a)swap(a,b);
        par[a]=b;
    }
}

int cnt=1;

int getcol(int v,int sk,int pr=-1){
    //cout<<"hey "<<v<<" "<<sk<<" "<<qan[sk][pr]<<" "<<qan[sk][v]<<" "<<pr<<endl;
    if (pr!=-1 && !col[ans[v]]){
        col[ans[v]]=true;
        if (qan[sk][pr]==qan[sk][v])return ans[v];
    }
    //cout<<1<<endl;
    trav(to,tree[v])if (to!=pr && ans[to]){

        int stac=getcol(to,sk,v);
        if (stac)return stac;
    }
    return 0;
}
vector<pir> kox;

int n;
void dfs(int v,int pr=-1){
    //cout<<"mta "<<v<<endl;
    if (pr!=-1){
        kox.ad({v,pr});
        tree[pr].ad(v);
        tree[v].ad(pr);
    }
    anc[v]=true;
    trav(to,g[v])if (!anc[to])dfs(to,v);

}

void dfs2(int v,int pr=-1){
    //cout<<v<<endl;
    ans[v]=getcol(v,v);
    if (ans[v]==0)ans[v]=cnt++;
    FORT(i,1,n)col[i]=false;
    trav(to,tree[v])if(to!=pr)dfs2(to,v);
    //cout<<v<<endl;
}

int main(){
    fastio;
    srng;
    int tp;
    cin>>tp;
    cin>>n;
    FORT(i,1,n)par[i]=i;
    FORT(i,1,n){
        FORT(j,1,n){
            cin>>qan[i][j];
            if (qan[i][j]==1)unite(i,j);
        }
    }
    FORT(i,1,n){
        FORT(j,1,n){
            int a=get(i),b=get(j);
            if (qan[i][j]==2){
                g[a].ad(b);
            }
        }
    }
    //cout<<1<<endl;
    dfs(1);
    dfs2(1);
    FORT(i,1,n)cout<<ans[get(i)]<<" ";
    cout<<endl;
    FORT(i,1,n){
        if (i!=get(i))
            cout<<i<<" "<<get(i)<<endl;
    }
    trav(tv,kox)cout<<tv.fr<<" "<<tv.sc<<endl;
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 688 ms 83436 KB Output is correct
3 Correct 689 ms 83576 KB Output is correct
4 Correct 782 ms 79004 KB Output is correct
5 Correct 727 ms 78780 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 36288 KB Output is correct
2 Correct 775 ms 81200 KB Output is correct
3 Correct 854 ms 36352 KB Output is correct
4 Correct 894 ms 36488 KB Output is correct
5 Correct 664 ms 41352 KB Output is correct
6 Correct 724 ms 36728 KB Output is correct
7 Correct 560 ms 31608 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 688 ms 83436 KB Output is correct
3 Correct 689 ms 83576 KB Output is correct
4 Correct 782 ms 79004 KB Output is correct
5 Correct 727 ms 78780 KB Output is correct
6 Correct 646 ms 36288 KB Output is correct
7 Correct 775 ms 81200 KB Output is correct
8 Correct 854 ms 36352 KB Output is correct
9 Correct 894 ms 36488 KB Output is correct
10 Correct 664 ms 41352 KB Output is correct
11 Correct 724 ms 36728 KB Output is correct
12 Correct 560 ms 31608 KB Output is correct
13 Correct 652 ms 36200 KB Output is correct
14 Correct 787 ms 39132 KB Output is correct
15 Correct 719 ms 45928 KB Output is correct
16 Correct 802 ms 42112 KB Output is correct
17 Correct 791 ms 39744 KB Output is correct
18 Correct 632 ms 40016 KB Output is correct
19 Correct 718 ms 52664 KB Output is correct
20 Correct 778 ms 46976 KB Output is correct
21 Correct 754 ms 47716 KB Output is correct
22 Correct 685 ms 39788 KB Output is correct
23 Correct 711 ms 39420 KB Output is correct
24 Correct 828 ms 39076 KB Output is correct
25 Correct 695 ms 41140 KB Output is correct