oj.uz

Submission #171403

# Submission time Handle Problem Language Result Execution time Memory
171403 2019-12-28T15:37:58 Z Swan Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 1097 ms 70420 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;

const int maxn = 10001;

vector<vector<int> > v;
bitset<maxn> in_cycle;
int color[maxn];
int par[maxn];
int dpth[maxn];
int lift[maxn][16];
int num[maxn];
int kek[maxn][maxn];
int pos_in_cycle[maxn];
vector<int> cycle;
int mx;
int ans;

void get_cycle(int u,int p = -1){
    color[u] = 1;
    par[u] = p;
    for(int i(0); i < v[u].size();i++){
        int to = v[u][i];
        if(color[to] == 2)continue;
        if(color[to] == 1 && to != par[u]){
            int now = u;
            in_cycle[to] = 1;
            while(now!=to){
                pos_in_cycle[now] = cycle.size();
                cycle.push_back(now);
                in_cycle[now] = 1;
                now = par[now];
            }
            pos_in_cycle[now] = cycle.size();
            cycle.push_back(now);
        }else if(!color[to]){
            get_cycle(to,u);
        }
    }
    color[u] = 2;
}

void build_tree(int u,int p = -1){
    if(p!=-1){
        lift[u][0] = p;
        dpth[u] = dpth[p]+1;
        num[u] = num[p];
    }else {
        lift[u][0] = u;
    }
    for(int i(1); i < 16;i++){
        lift[u][i] = lift[lift[u][i-1]][i-1];
    }
    for(int i(0); i < v[u].size();i++){
        int to = v[u][i];
        if(to == p || in_cycle[to])continue;
        build_tree(to,u);
    }
}

int get_lca(int x,int y){
    if(dpth[x] > dpth[y])swap(x,y);
    int delta = abs(dpth[x]-dpth[y]);
    for(int i(0); i < 17;i++){
        int bit = delta&(1<<i);
        if(!bit)continue;
        y = lift[y][i];
    }
    if(x == y)return x;
    for(int i(15);i>=0;i--){
        if(lift[x][i]!=lift[y][i]){
            x = lift[x][i];
            y = lift[y][i];
        }
    }
    return lift[x][0];
}

int get_dist(int x,int y){
    int dist = 0;
    if(num[x] == num[y]){
        int lca = get_lca(x,y);
        kek[x][y] = lca;
        dist = dpth[x]+dpth[y]-2*dpth[lca];
    }else{
        dist = dpth[x]+dpth[y];
        int fst = pos_in_cycle[num[x]];
        int snd = pos_in_cycle[num[y]];
        if(fst > snd)swap(fst,snd);
        int a = abs(snd-fst);
        int b = cycle.size()-snd+fst;
        dist+=min(a,b);
    }
    return dist;
}

void solve(int x,int y){
    int dist = 0;
    if(num[x] == num[y]){
        int lca = kek[x][y];
        dist = dpth[x]+dpth[y]-2*dpth[lca];
        if(dist == mx)ans++;
    }else{
        dist = dpth[x]+dpth[y];
        int fst = pos_in_cycle[num[x]];
        int snd = pos_in_cycle[num[y]];
        if(fst > snd)swap(fst,snd);
        int a = snd-fst;
        int b = cycle.size()-snd+fst;
        if(dist+a == mx && a == min(a,b)){
            ans++;
            //cout << "a " << x+1 << ' ' << y+1 << endl;
        }
        if(dist+b == mx && b == min(a,b)){
            ans++;
            //cout << "b " << x+1 << ' ' << y+1 << ' ' <<b << ' ' << dist << endl;
        }
    }
}

main(){
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    v.resize(n+2);
    for(int i(0); i < n;i++){
        int a,b; cin >> a >> b;
        a--;b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    get_cycle(0,0);
    for(int i(0); i < n;i++){
        if(in_cycle[i]){
            num[i] = i;
            build_tree(i);
        }
    }
    for(int i(0); i < n;i++){
        for(int j(i+1); j < n;j++){
            mx = max(mx,get_dist(i,j));
        }
    }
    for(int i(0); i< n;i++){
        for(int j(i+1); j < n;j++){
            solve(i,j);
        }
    }
    cout << ans;
    return 0;
}
/*
*/

Compilation message

shymbulak.cpp: In function 'void get_cycle(int, int)':
shymbulak.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void build_tree(int, int)':
shymbulak.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:126:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 1016 KB Output is correct
14 Correct 9 ms 2936 KB Output is correct
15 Correct 7 ms 2168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 26 ms 4984 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 21 ms 5112 KB Output is correct
5 Correct 184 ms 23900 KB Output is correct
6 Correct 824 ms 70420 KB Output is correct
7 Correct 1097 ms 70344 KB Output is correct
8 Correct 974 ms 70292 KB Output is correct
9 Correct 144 ms 22332 KB Output is correct
10 Correct 417 ms 33784 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 11000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -