oj.uz

Submission #13128

# Submission time Handle Problem Language Result Execution time Memory
13128 2015-01-31T14:32:57 Z gs14004 Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 1500 ms 20704 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;

int n;
vector<int> graph[200005];

int low[200005], dfn[200005], piv;
int is_cyc[200005];

void dfs(int x, int pa){
    low[x] = dfn[x] = ++piv;
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i] == pa) continue;
        if(dfn[graph[x][i]]){
            is_cyc[graph[x][i]] = 1;
            low[x] = min(low[x],dfn[graph[x][i]]);
        }
        else{
            dfs(graph[x][i],x);
            low[x] = min(low[x],low[graph[x][i]]);
        }
    }
    if(low[x] < dfn[x]) is_cyc[x] = 1;
}

pi bfs(int x){
    queue<int> q,p,dist;
    q.push(x);
    p.push(0);
    dist.push(0);
    pi ret(0ll,0);
    while (!q.empty()) {
        int qf = q.front();
        int pf = p.front();
        int df = dist.front();
        q.pop();
        p.pop();
        dist.pop();
        ret = max(ret,pi(df,qf));
        for (int i=0; i<graph[qf].size(); i++) {
            int pos = graph[qf][i];
            if(is_cyc[pos] || pos == pf) continue;
            q.push(pos);
            p.push(qf);
            dist.push(df+1);
        }
    }
    return ret;
}

int nxt[200005], far[200005], bef[200005];

void solve(){
    int start_pos = 0, ret = 0, cnt = 0;
    for (int i=1; i<=n; i++) {
        if(is_cyc[i]) start_pos = i, cnt++;
    }
    int pos = start_pos, par = 0;
    int size = 0;
    do{
        is_cyc[pos] = 0;
        pi x = bfs(pos);
        far[pos] = x.first;
        ret = max(ret,bfs(x.second).first);
        is_cyc[pos] = 1;
        for (int i=0; i<graph[pos].size(); i++) {
            if(graph[pos][i] == par) continue;
            if(is_cyc[graph[pos][i]]){
                nxt[pos] = graph[pos][i];
                par = pos;
                pos = nxt[pos];
                bef[pos] = par;
                break;
            }
        }
        size++;
    }while (pos != start_pos);
    
    do{
        int pos2 = nxt[pos], i = 1;
        while (pos2 != pos) {
            ret = max(ret,far[pos] + far[pos2] + min(i,cnt-i));
            i++;
            pos2 = nxt[pos2];
        }
        pos = nxt[pos];
    }while (pos != start_pos);
    
    printf("%d",ret);
}

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(1,0);
    solve();
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 10960 KB Output isn't correct
2 Incorrect 2 ms 10960 KB Output isn't correct
3 Incorrect 3 ms 10960 KB Output isn't correct
4 Incorrect 0 ms 10960 KB Output isn't correct
5 Incorrect 0 ms 10960 KB Output isn't correct
6 Incorrect 0 ms 10960 KB Output isn't correct
7 Incorrect 2 ms 10960 KB Output isn't correct
8 Incorrect 0 ms 10960 KB Output isn't correct
9 Incorrect 0 ms 10960 KB Output isn't correct
10 Incorrect 0 ms 10960 KB Output isn't correct
11 Incorrect 0 ms 10960 KB Output isn't correct
12 Incorrect 0 ms 10960 KB Output isn't correct
13 Incorrect 0 ms 10960 KB Output isn't correct
14 Incorrect 0 ms 10960 KB Output isn't correct
15 Incorrect 0 ms 10960 KB Output isn't correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10960 KB Output isn't correct
2 Incorrect 0 ms 10960 KB Output isn't correct
3 Incorrect 4 ms 10960 KB Output isn't correct
4 Incorrect 0 ms 10960 KB Output isn't correct
5 Incorrect 2 ms 11092 KB Output isn't correct
6 Incorrect 0 ms 11092 KB Output isn't correct
7 Incorrect 0 ms 11092 KB Output isn't correct
8 Incorrect 5 ms 11092 KB Output isn't correct
9 Incorrect 3 ms 11092 KB Output isn't correct
10 Incorrect 4 ms 11092 KB Output isn't correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 14256 KB Output isn't correct
2 Incorrect 61 ms 15180 KB Output isn't correct
3 Execution timed out 1500 ms 16992 KB Program timed out
4 Incorrect 52 ms 14128 KB Output isn't correct
5 Incorrect 26 ms 14128 KB Output isn't correct
6 Incorrect 123 ms 17556 KB Output isn't correct
7 Incorrect 49 ms 16900 KB Output isn't correct
8 Incorrect 119 ms 17296 KB Output isn't correct
9 Incorrect 110 ms 17296 KB Output isn't correct
10 Incorrect 489 ms 17744 KB Output isn't correct
11 Incorrect 104 ms 20168 KB Output isn't correct
12 Incorrect 134 ms 20704 KB Output isn't correct