Submission #234516

#	Time	Username	Problem	Language	Result	Execution time	Memory
234516		shayan_p	Izlet (COI19_izlet)	C++14	100 / 100	847 ms	62072 KiB

izlet

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3010, mod = 1e9 + 7, inf = 1e9 + 10;

int a[maxn][maxn];
bool adj[maxn][maxn];
vector<int> vec;

vector<int> comp[maxn];
int C;

bool mark[maxn];
int up[maxn], h[maxn];

int n;

void prep(int u){
    mark[u] = 1;
    up[u] = h[u];
    for(int y = 1; y <= n; y++){
	if(!mark[y] && adj[u][y]){
	    h[y] = h[u] + 1;
	    prep(y);
	    up[u] = min(up[u], up[y]);
	}
	else if(adj[u][y]){
	    up[u] = min(up[u], h[y]);
	}
    }
}
void dfs(int u){
    mark[u] = 1;
    vec.PB(u);
    for(int y = 1; y <= n; y++){
	if(!mark[y] && adj[u][y]){
	    int SZ = sz(vec);
	    dfs(y);
	    if(up[y] >= h[u]){
		while(sz(vec) > SZ){
		    comp[C].PB(vec.back());
		    vec.pop_back();
		}
		comp[C].PB(u);
		C++;
	    }
	}
    }
}

int pr[maxn];
int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
    if((a = fnd(a)) == (b = fnd(b)))
	return;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
}

vector<int> v[maxn];

int ans[maxn];

vector<int> path;

void DFS(int u, int par = -1){
    path.PB(u);

    if(sz(path) > 2){
	int A = a[path[1]][path[sz(path)-1]];
	int B = a[path[0]][path[sz(path)-2]];
	int C = a[path[1]][path[sz(path)-2]];
	int D = a[path[0]][path[sz(path)-1]];
	if(A == D && B == D && C == D-1)
	    mrg(path[0], u);
    }
    if(sz(path) == 2 && a[path[0]][u] == 1){
	mrg(path[0], u);
    }

    for(int y : v[u]){
	if(y != par)
	    DFS(y, u);
    }
    path.pop_back();
}

vector<pii> ED;

void adde(int a, int b){
    v[a].PB(b);
    v[b].PB(a);
    ED.PB({a, b});
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    memset(pr, -1, sizeof pr);
    
    int _;
    cin >> _;
    
    cin >> n;
    for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
	    cin >> a[i][j];
    for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
	    if(a[i][j] == 1)
		mrg(i, j);
    for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
	    if(a[i][j] == 2)
		adj[fnd(i)][fnd(j)] = 1;
    prep(fnd(1));
    memset(mark, 0, sizeof mark);
    dfs(fnd(1));
    assert(sz(vec) == 1);    
    for(int i = 1; i <= n; i++)
	if(fnd(i) != i)
	    adde(i, fnd(i));
    for(int i = 0; i < C; i++)
	for(int j = 0; j < sz(comp[i])-1; j++)
	    adde(comp[i][j], comp[i][j+1]);
    
    memset(pr, -1, sizeof pr);
    for(int i = 1; i <= n; i++){
	DFS(i);
    }
    for(int i = 1; i <= n; i++){
	cout << fnd(i) << " ";
    }
    cout << "\n";
    for(pii p : ED){
	cout << p.F << " " << p.S << "\n";
    }   
    return 0;
}

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