oj.uz

Submission #234516

# Submission time Handle Problem Language Result Execution time Memory
234516 2020-05-24T11:31:43 Z shayan_p Izlet (COI19_izlet) C++14
100 / 100
 847 ms 62072 KB 
// 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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 661 ms 60816 KB Output is correct
3 Correct 639 ms 60792 KB Output is correct
4 Correct 687 ms 59128 KB Output is correct
5 Correct 775 ms 62072 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 44280 KB Output is correct
2 Correct 744 ms 60920 KB Output is correct
3 Correct 798 ms 60856 KB Output is correct
4 Correct 783 ms 48444 KB Output is correct
5 Correct 659 ms 55020 KB Output is correct
6 Correct 669 ms 42560 KB Output is correct
7 Correct 512 ms 36408 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 661 ms 60816 KB Output is correct
3 Correct 639 ms 60792 KB Output is correct
4 Correct 687 ms 59128 KB Output is correct
5 Correct 775 ms 62072 KB Output is correct
6 Correct 690 ms 44280 KB Output is correct
7 Correct 744 ms 60920 KB Output is correct
8 Correct 798 ms 60856 KB Output is correct
9 Correct 783 ms 48444 KB Output is correct
10 Correct 659 ms 55020 KB Output is correct
11 Correct 669 ms 42560 KB Output is correct
12 Correct 512 ms 36408 KB Output is correct
13 Correct 842 ms 46132 KB Output is correct
14 Correct 847 ms 46464 KB Output is correct
15 Correct 731 ms 53596 KB Output is correct
16 Correct 758 ms 41508 KB Output is correct
17 Correct 726 ms 42264 KB Output is correct
18 Correct 711 ms 55200 KB Output is correct
19 Correct 731 ms 54540 KB Output is correct
20 Correct 716 ms 52856 KB Output is correct
21 Correct 692 ms 44664 KB Output is correct
22 Correct 681 ms 45052 KB Output is correct
23 Correct 722 ms 44024 KB Output is correct
24 Correct 781 ms 44280 KB Output is correct
25 Correct 633 ms 44280 KB Output is correct