oj.uz

답안 #580551

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580551 2022-06-21T12:26:33 Z FatihSolak 관광지 (IZhO14_shymbulak) C++17
50 / 100
 1500 ms 10304 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
bool on_cycle[N];
int par[N];
int vis[N];
int dep[N];
pair<int,int> maxi[N];
vector<int> cycle;
pair<int,long long> merge(pair<int,long long> a,pair<int,long long> b){
    pair<int,long long> ret = {0,0};
    ret.first = max(a.first,b.first);
    if(a.first == ret.first)ret.second += a.second;
    if(b.first == ret.first)ret.second += b.second;
    return ret;
}
pair<int,long long> merge2(pair<int,long long> a,pair<int,long long> b){
    return {a.first + b.first,a.second*b.second};
}
struct SegTree{
    vector<pair<int,long long>> t;
    int n;
    SegTree(int size){
        n = size;
        t.assign(4*n,{-1e9,0});
    }
    void upd(int v,int tl,int tr,int pos,pair<int,long long> val){
        if(tl == tr){
            t[v] = merge(t[v],val);
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm)
            upd(v*2,tl,tm,pos,val);
        else upd(v*2+1,tm+1,tr,pos,val);
        t[v] = merge(t[v*2],t[v*2+1]);
    }
    pair<int,long long> get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl)
            return {-1e9,0};
        if(l <= tl && tr <= r)
            return t[v];
        int tm = (tl + tr)/2;
        return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
    }
    void upd(int pos,pair<int,long long> val){
        upd(1,0,n,pos,val);
    }
    pair<int,long long> get(int l,int r){
        return get(1,0,n,l,r);
    }
};
void dfs(int v,int pr){
    vis[v] = 1;
    par[v] = pr;
    for(auto u:adj[v]){
        if(u == pr)continue;
        if(cycle.size())return;
        if(vis[u] == 1){
            while(1){
                on_cycle[v] = 1;
                cycle.push_back(v);
                if(u == v)break;
                v = par[v];
            }
        }
        if(cycle.size())return;
        dfs(u,v);
    }
    vis[v] = 2;
}
pair<int,long long> res;
void dfs1(int v,int pr,int c){
    maxi[v] = {dep[v],1};
    par[v] = c;
    for(auto u:adj[v]){
        if(u == pr || on_cycle[u])continue;
        dep[u] = dep[v] + 1;
        dfs1(u,v,c);
        res = merge(res,{maxi[v].first + maxi[u].first - 2*dep[v],maxi[v].second * maxi[u].second});
        maxi[v] = merge(maxi[v],maxi[u]);
    }
}
pair<int,long long> get_diameter_and_count(int v,int x){
    res = {0,0};
    dfs1(v,0,x);
    return res;
}
void solve(){
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    for(int i = 0;i<cycle.size();i++){
        get_diameter_and_count(cycle[i],i);
        //cout << cycle[i] << " ";
    }
    //cout << endl;
    int ans1 = 0,ans2 = 0;
    for(int i = 1;i<=n;i++){
        vector<int> d(n+1,-1);
        queue<int> q;
        q.push(i);
        d[i] = 0;
        while(q.size()){
            auto tp = q.front();
            q.pop();
            for(auto u:adj[tp]){
                if(d[u] == -1){
                    q.push(u);
                    d[u] = d[tp] + 1;
                }
            }
        }
        for(int j = 1;j<=n;j++){
            if(d[j] > ans1){
                ans1 = d[j];
                ans2 = 0;
            }
            if(d[j] == ans1)ans2++;
            if(d[j] == ans1 && (cycle.size()%2 == 0) && (par[j] == (par[i] + cycle.size()/2)%cycle.size()))ans2++;
        }
    }
    cout << ans2/2;
}
    
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

shymbulak.cpp: In function 'void solve()':
shymbulak.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0;i<cycle.size();i++){
      |                   ~^~~~~~~~~~~~~
shymbulak.cpp:127:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             if(d[j] == ans1 && (cycle.size()%2 == 0) && (par[j] == (par[i] + cycle.size()/2)%cycle.size()))ans2++;
      |                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5048 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 7 ms 5076 KB Output is correct
15 Correct 6 ms 5092 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 5144 KB Output is correct
2 Correct 11 ms 5076 KB Output is correct
3 Correct 21 ms 5076 KB Output is correct
4 Correct 20 ms 5076 KB Output is correct
5 Correct 419 ms 5304 KB Output is correct
6 Correct 322 ms 5352 KB Output is correct
7 Correct 498 ms 5312 KB Output is correct
8 Correct 477 ms 5332 KB Output is correct
9 Correct 425 ms 5332 KB Output is correct
10 Correct 500 ms 5320 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1582 ms 10304 KB Time limit exceeded
2 Halted 0 ms 0 KB -