oj.uz

Submission #12818

# Submission time Handle Problem Language Result Execution time Memory
12818 2015-01-06T07:22:12 Z dohyun0324 Dreaming (IOI13_dreaming) C++
0 / 100
 101 ms 14908 KB 
#include "dreaming.h"
#include<algorithm>
#include<vector>
using namespace std;
int maxx,t,dap,s[100010],w,arr[200010],top,ch[100010],len[100010],pos[100010],all,big1[100010],big2[100010];
vector<int>d[100010];
struct data{
    int x,y,c;
    bool operator<(const data&r)const{
        return x<r.x;
    }
}con[200010];
void dfs1(int x,int cost)
{
    int i;
    ch[x]=1;
    if(maxx<cost) maxx=cost, t=x;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]) continue;
        dfs1(con[i].y,cost+con[i].c);
        d[x].push_back(big1[con[i].y]+con[i].c);
    }
    int p=0;
    for(i=0;i<d[x].size();i++){
        if(big1[x]<d[x][i]){big1[x]=d[x][i]; p=i;}
    }
    for(i=0;i<d[x].size();i++){
        if(big2[x]<d[x][i] && i!=p) big2[x]=d[x][i];
    }
}
void dfs2(int x,int gap)
{
    int i;
    ch[x]=2;
    if(dap>max(big1[x],gap)) dap=max(big1[x],gap);
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==2) continue;
        int maxi=0;
        if(big1[x]==d[x][s[x]]) maxi=max(gap,big2[x]);
        else maxi=max(gap,big1[x]);
        dfs2(con[i].y,maxi+con[i].c);
        s[x]++;
    }
}
void dfs(int x,int cost)
{
    int i;
    ch[x]=3;
    if(maxx<cost) maxx=cost, t=x;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==3) continue;
        dfs(con[i].y,cost+con[i].c);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int i,ans=0;
    for(i=0;i<M;i++)
    {
        A[i]++; B[i]++;
        w++; con[w].x=A[i]; con[w].y=B[i]; con[w].c=T[i];
        w++; con[w].x=B[i]; con[w].y=A[i]; con[w].c=T[i];
    }
    sort(con+1,con+w+1);
    for(i=1;i<=w;i++)
    {
        if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
    }
    for(i=1;i<=N;i++)
    {
        if(ch[i]==0)
        {
            dap=2147483647; maxx=0;
            dfs1(i,0);
            dfs2(i,0);
            maxx=0; dfs(t,0);
            if(ans<maxx) ans=maxx;
            arr[++top]=dap;
        }
    }
    sort(arr+1,arr+top+1);
    return max(ans,max(arr[top]+arr[top-1]+L,arr[top-1]+arr[top-2]+L*2));
}

Compilation message

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<d[x].size();i++){
             ~^~~~~~~~~~~~
dreaming.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<d[x].size();i++){
             ~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 14908 KB Output is correct
2 Correct 90 ms 14584 KB Output is correct
3 Correct 59 ms 12448 KB Output is correct
4 Correct 14 ms 4480 KB Output is correct
5 Correct 11 ms 3812 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 14908 KB Output is correct
2 Correct 90 ms 14584 KB Output is correct
3 Correct 59 ms 12448 KB Output is correct
4 Correct 14 ms 4480 KB Output is correct
5 Correct 11 ms 3812 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 14908 KB Output is correct
2 Correct 90 ms 14584 KB Output is correct
3 Correct 59 ms 12448 KB Output is correct
4 Correct 14 ms 4480 KB Output is correct
5 Correct 11 ms 3812 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6520 KB Output is correct
2 Correct 29 ms 6576 KB Output is correct
3 Correct 29 ms 6512 KB Output is correct
4 Correct 28 ms 6520 KB Output is correct
5 Correct 28 ms 6528 KB Output is correct
6 Correct 30 ms 6656 KB Output is correct
7 Correct 28 ms 6656 KB Output is correct
8 Correct 29 ms 6392 KB Output is correct
9 Correct 27 ms 6400 KB Output is correct
10 Correct 29 ms 6648 KB Output is correct
11 Correct 4 ms 2816 KB Output is correct
12 Correct 8 ms 4608 KB Output is correct
13 Correct 8 ms 4608 KB Output is correct
14 Correct 7 ms 4480 KB Output is correct
15 Correct 8 ms 4608 KB Output is correct
16 Correct 11 ms 4480 KB Output is correct
17 Correct 7 ms 3840 KB Output is correct
18 Correct 8 ms 4736 KB Output is correct
19 Correct 8 ms 4480 KB Output is correct
20 Incorrect 5 ms 2688 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 14908 KB Output is correct
2 Correct 90 ms 14584 KB Output is correct
3 Correct 59 ms 12448 KB Output is correct
4 Correct 14 ms 4480 KB Output is correct
5 Correct 11 ms 3812 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 14908 KB Output is correct
2 Correct 90 ms 14584 KB Output is correct
3 Correct 59 ms 12448 KB Output is correct
4 Correct 14 ms 4480 KB Output is correct
5 Correct 11 ms 3812 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -