Submission #171396

#	Time	Username	Problem	Language	Result	Execution time	Memory
171396		Swan	Shymbulak (IZhO14_shymbulak)	C++14	50 / 100	1117 ms	68188 KiB

shymbulak

#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 = 5001;

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 (stderr)

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50