2 5 3
01
0
11
10001

ans: 0

Edited by author 26.06.2007 18:43

Each of the cameramen wants Lev to skate along a segment of a straight line from some point to another (and each has specified his own pair of points). Lev has decided to skate along all the specified segments passing from a segment to a segment along a circular arc so that his trajectory has the shape of a smooth curve.

Do Lev move in a circular arc or a straight line?

If there is no arc connecting two consecutive directed segments without breaks, Lev can extend one of the segments so as to connect them by an arc.

For example 2, do these circles valid to this statement?
(-1,-1) radius = sqrt(26)
(1,1) radius = 3*sqrt(2)
(0,0) radius = 2*sqrt(5)

but (-2,-2) radius = 6 is invalid because the endpoint of the segment doesn't end in this circle.
Am I right?

And Finally how do you compute 7.1415926536?
because I find that circle (-1,-1) could yield better solution for about 6.69659557624

If anyone know hint or test case for test#13

why?

Can anyone explain me how we got the sample input ?

why "2 1 1 -2", or "2 1 1 0" is not an answer ?

when i submit i have fail(checker). What can I do with that?

if the "ss" answer equal 60,
update to 0 and change mm = mm+1

:)

The fastest way is to use matrix exponentiation and it is quite simple to understand. The algorithm is O(log n), yes it is that fast!. I got AC with Python 2.7 with 0.046s. Python has an added advantage for this problem since its Integer type can be as big as the RAM of the device being used. With c++ you can still get answers fast, using matrix exponentiation, but the answers are not precise enough, and leads to WA.

Edited by author 29.07.2015 15:42

care about -0.0

plz, help me! why i get crash(access violation).
// LCA (least common ancestor) offline by using interval tree in O(logN)
// Solution by Serekov Abzal

#pragma comment(linker, "/STACK:16777216")

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>

using namespace std;
int ADD = 65536;
int inf = 9999999;
vector <vector <pair<int, int> > > graph;
vector <bool> b(50001, false);
vector <int> h(50001, 0);
vector <int> order;
vector <int> d(50001, 0);
vector <int> first(50001, -1);
pair <int, int> tree[2 * 65536 + 1];
int n, root = 0;
void init_graph()
{
    scanf("%d", &n);
    graph.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }
};
void dfs(int v, int p)
{
    b[v] = true;
    h[v] = p;
    order.push_back(v);
    for (int i = 0; i < graph[v].size(); i++)
        if (!b[graph[v][i].first])
        {
            dfs(graph[v][i].first, p + 1);
            order.push_back(v);
        }
};
void bfs(int v)
{
    queue <int> Q;
    Q.push(v);
    while (!Q.empty())
    {
        int u = Q.front();
        b[u] = true;
        for (int i = 0; i < graph[u].size(); i++)
            if (!b[graph[u][i].first])
            {
                d[graph[u][i].first] = d[u] + graph[u][i].second;
                Q.push(graph[u][i].first);
            }
        Q.pop();
    }
};
void prepare()
{
    h[root] = 0;
    dfs(root, 0);
    for (int i = 0; i < order.size(); i++)
        if (first[order[i]] == -1)
            first[order[i]] = i;
    for (int i = 0; i < n; i++) b[i] = false;
    d[root] = 0;
    bfs(root);
};
int minimum(int u, int v)
{
    int l = u, r = v, ans = inf, ver = inf;
    while (l <= r)
    {
        if (l % 2 == 1)
        {
            if (tree[l].second < ans)
            {
                ans = tree[l].second;
                ver = tree[l].first;
            }
            l++;
        };
        if (r % 2 == 0)
        {
            if (tree[r].second < ans)
            {
                ans = tree[r].second;
                ver = tree[r].first;
            }
            --r;
        }
        l/=2; r/=2;
    }
    return ver;
};
int lca(int u, int v)
{
    int l = first[u] + ADD, r = first[v] + ADD;
    return minimum(l, r);
};
void init_zaprosi()
{
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int ans = d[u] + d[v] - 2 * d[lca(u, v)];
        printf("%d\n", ans);
    }
};
void tree_build()
{
    for (int i = 0; i <= 2 * ADD; i++)
    tree[i] = make_pair(-1, inf);

    for (int i = ADD; i < ADD + order.size(); i++)
    {
        tree[i].first = order[i - ADD];
        tree[i].second = h[order[i - ADD]];
    }
    for (int i = ADD - 1; i > 0; i--)
    {
        if (tree[2 * i].first == -1 || tree[2 * i + 1].first == -1)
        {
            if (!(tree[2 * i].first == -1 && tree[2 * i + 1].first == -1))
            {
                if (tree[2 * i].first == -1) tree[i] = tree[2 * i + 1]; else tree[i] = tree[2 * i];
            }
        }
        else
        {
            if (tree[2 * i].second < tree[2 * i + 1].second) tree[i] = tree[2 * i];    else tree[i] = tree[2 * i + 1];
        }
    }
};
int main()
{
    init_graph();
    prepare();
    tree_build();
    init_zaprosi();
    return 0;
}

This is very easy problem. You can use:
1) BFS or DFS to find the components of the graph;
2) Prim or Kruskal algo for minimum spanning tree.

Can you be more explicit about the error?
I used lots of test cases from discussions and code show's correct results without errors.
Do you need me to post my solution?

Edited by author 29.07.2015 13:55

给二分查找的参数传错了，传的是m。
弄得我都快崩溃了。
不过还好看了解答发现了。
下面是C代码
**********************************************************************************************
#include<stdio.h>
int teacher[15001]={0};
int exist_temp(int temp,int m){
    int first=0,last=m-1,count=0;
    while(first<=last){
        int mid=(first+last)/2;
        if(teacher[mid]==temp){
            count++;
            return count;
        }
        else{
            if(teacher[mid]>temp) last=mid-1;
            else first=mid+1;
        }
    }
    return count;
}
int main(){
    int n,m,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&teacher[i]);
    scanf("%d",&m);
    int count=0,hi=m;
    while(hi--){
        int temp;
        scanf("%d",&temp);
        if(exist_temp(temp,n)!=0)
            count++;
    }
    printf("%d\n",count);
    return 0;
}

I'm using dfs and can't find test for my program :(

Edited by author 02.08.2012 16:46

Is a root node for the tree?

Subj

can somebody explain how the example shown has answer as
6 33
and not
6 44?
are we not supposed to give the word position?

3 3
1 2
2 3
3 1
1 3
how is this possible?
from 1 to 2 there is an uphill road...from 2 to 3 there is also an uphill road...then how can there be a uphill road from 3 to 1??from 3 to 1 there should be a downhill road...
correct me if i am wrong..

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;


 public class main
 {

 public static Scanner in = new Scanner(System.in);

 public static void main(String[] args)
 {
   int candidates = in.nextInt();
   int electors = in.nextInt();
   int votes[] = new int[electors];
   int summ = 0;
   double onePercent = (double) electors / 100;

   for(int x = 0; x < electors; x++)
   {
     votes[x] = in.nextInt();
   }

   Arrays.sort(votes);
   int VoteNum = 1;
   int startOfNextSearch = 0;

   while(candidates != 0)
   {
   for(int x = startOfNextSearch; x < electors; x++)
   {
    if(x > startOfNextSearch && votes[x] == votes[x -1] && votes[x] == VoteNum)
    {
      summ++;
    }
    else if(votes[x] == VoteNum)
    {
    summ++;
    }
    else
    {
    x = electors;
    }
    }
    BigDecimal  Part = new BigDecimal(Double.toString((double) summ / onePercent));
    Part = Part.setScale(2, BigDecimal.ROUND_HALF_UP);
    if((Part.doubleValue() + 1) % 1 == 0)
    {
      System.out.println(Part.doubleValue() + "0%");
    }
    else
    {
      System.out.println(Part.doubleValue() + "%");
    }
    VoteNum++;
    startOfNextSearch += summ ;
    summ = 0;
    candidates--;
    }

  }
}


Edited by author 26.07.2015 16:16

ok...i solved my TLE 6 and TLE 7 problems, now i think it s more than fast enough
but i god WA#1 even though it gives good answers too all tests on my machine....

any ideas what s wrong ? can someone give me test 1 ?


#include<iostream>
#include<vector>

using namespace std;

int main(){

    vector<char> tab;
    char x, previous;
    int size=0,j=0;
    while(!(cin >> x).eof()){
          if(x!=previous){
                   tab.push_back(x);
                   j++;
                   previous=x;
                   }
          else{
               tab.pop_back();
               j--;
               if(j>=1)
               previous = tab[j-1];
               else
               previous = '!';
              }
          }
    for( int i = 0; i < tab.size(); i++ ){
         cout << tab[ i ];
         }
    getchar();getchar();
}

Edited by author 09.08.2011 19:27