oj.uz

Submission #40474

# Submission time Handle Problem Language Result Execution time Memory
40474 2018-02-01T21:47:47 Z igzi Tropical Garden (IOI11_garden) C++11
0 / 100
 8 ms 6392 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define maxN 150005
#define INF LLONG_MAX
#define pll pair<long long,long long>

using namespace std;

vector <int> adj[maxN];
long long N,P,s,i,dis[maxN],k[maxN];
void dijkstra(int x){
priority_queue <pll, vector<pll>, greater<pll> >pq;
bool mar[maxN];
for(i=0;i<maxN;i++){
dis[i]=INF;
mar[i]=false;
k[i]=0;
}
pq.push({0,x});
dis[x]=0;
while(!pq.empty()){
    long long v=pq.top().second;
    pq.pop();
    if(mar[v]) continue;
    mar[v]=true;
    for(i=0;i<adj[v].size();i++){
        if(adj[adj[v][i]].size()>0 && adj[adj[v][i]][0]==v){
            if(dis[adj[v][i]]>dis[v]+1){
               dis[adj[v][i]]=dis[v]+1;
               pq.push({dis[adj[v][i]],adj[v][i]});
               if(v!=P) k[adj[v][i]]=k[v];
               else {
                if(i==0) k[adj[v][i]]=0;
                else k[adj[v][i]]=1;
               }
            }
        }
        if(adj[adj[v][i]].size()>1 && adj[adj[v][i]][1]==v && adj[adj[adj[v][i]][0]].size()==1){
            if(dis[adj[adj[v][i]][0]]>dis[v]+2){
               dis[adj[adj[v][i]][0]]=dis[v]+2;
               pq.push({dis[adj[adj[v][i]][0]],adj[adj[v][i]][0]});
               if(v!=P) k[adj[adj[v][i]][0]]=k[v];
               else {
                if(i==0) k[adj[adj[v][i]][0]]=0;
                else k[adj[adj[v][i]][0]]=1;
               }
            }
        }
    }
}
}
long long period(int x,int d){
if(d>3*N) return INF;
int y;
if(adj[x].size()>0 && (adj[x][0]!=s || adj[x].size()==1)) y=adj[x][0];
else y=adj[x][1];
if(y==P) return d+1;
s=x;
return period(y,d+1);
}

void count_routes(int n,int m,int p,int r[][2],int q,int g[]){
N=n;
P=p;
for(i=0;i<m;i++){
    adj[r[i][0]].push_back(r[i][1]);
    adj[r[i][1]].push_back(r[i][0]);
}
dijkstra(p);
long long t1,t2;
s=-5;
t1=period(p,0);
if(adj[p].size()>0) {
    s=adj[p][0];
    t2=period(p,0);
}
else t2=INF;
for(i=0;i<q;i++){
    long long ans=0;
    for(int j=0;j<n;j++){
        if(k[j]==1 && (dis[j]-g[i])%t1==0 && dis[j]<=g[i] && dis[j]!=INF) ans++;
        if(k[j]==0 && (dis[j]-g[i])%t2==0 && dis[j]<=g[i] && dis[j]!=INF) ans++;
    }
    answer(ans);
}
}

Compilation message

garden.cpp: In function 'void dijkstra(int)':
garden.cpp:27:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<adj[v].size();i++){
             ~^~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6392 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 8 ms 6340 KB Output is correct
4 Correct 8 ms 6364 KB Output is correct
5 Correct 7 ms 6368 KB Output is correct
6 Incorrect 8 ms 6392 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6392 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 8 ms 6340 KB Output is correct
4 Correct 8 ms 6364 KB Output is correct
5 Correct 7 ms 6368 KB Output is correct
6 Incorrect 8 ms 6392 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6392 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 8 ms 6340 KB Output is correct
4 Correct 8 ms 6364 KB Output is correct
5 Correct 7 ms 6368 KB Output is correct
6 Incorrect 8 ms 6392 KB Output isn't correct
7 Halted 0 ms 0 KB -