oj.uz

Submission #26746

# Submission time Handle Problem Language Result Execution time Memory
26746 2017-07-05T11:11:41 Z model_code Programming Contest (POI11_pro) C++11
100 / 100
 59 ms 3328 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Konkurs programistyczny                          *
 *   Autor:             Tomasz Idziaszek                                 *
 *   Zlozonosc czasowa: O(m^3 n)                                         *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                      przez sciezki polepszajace koszt                 *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
#define FORE(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

const int N=600;
int n,m,r,t,k;
vector<int> adj[N],adj_m[N];
int deg[N],ma_m[N];
int u[N],u_m[N];


int dfs(int v, int d) {
   if (deg[v] < d-1) return true;
   FORE(i,adj[v]) if (!u_m[*i] && ma_m[*i] == v) {
      u_m[*i]=1;
      FORE(j,adj_m[*i]) if (!u[*j] && *j != v) {
	 u[*j]=1;
	 if (dfs(*j, d)) {
	    ma_m[*i] = *j;
	    ++deg[*j];
	    --deg[v];
	    return true;
	 }
      }
   }
   return false;
}

int rob() {
   REP(i,n) deg[i]=0;
   REP(i,m) ma_m[i]=-1;
   REP(i,m)
      if (!adj_m[i].empty()) {
	 ma_m[i]=adj_m[i][0];
	 ++deg[adj_m[i][0]];
      }

   int ch=1;
   while (ch) {
      ch=0;
      REP(j,n) u[j]=0;
      REP(j,m) u_m[j]=0;
      vector<pair<int,int> > vv;
      REP(i,n) vv.push_back(make_pair(-deg[i],i));
      sort(vv.begin(),vv.end());
      REP(i,n)
	 if (dfs(vv[i].second, -vv[i].first))
	    ch=1;
   }
   return 0;
}


int main() {
   scanf("%d%d%d%d%d",&n,&m,&r,&t,&k);
   REP(i,k) {
      int a,b;
      scanf("%d%d",&a,&b);
      --a;
      --b;
      adj[a].push_back(b);
      adj_m[b].push_back(a);
   }
   REP(i,m) random_shuffle(adj_m[i].begin(), adj_m[i].end());

   rob();

   int ile=0;
   int koszt=0;
   int degi[n];
   REP(i,n) {
      int w = degi[i] = min(deg[i], t/r);
      ile += w;
      koszt += (1+w)*w/2*r;
   }
   printf("%d %d\n",ile,koszt);
   REP(i,m) {
      if (ma_m[i]!=-1 && --degi[ ma_m[i] ] >= 0)
	 printf("%d %d %d\n",ma_m[i]+1,i+1,r*degi[ma_m[i]]);
   }
}

Compilation message

pro.cpp: In function 'int main()':
pro.cpp:71:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d%d%d",&n,&m,&r,&t,&k);
                                      ^
pro.cpp:74:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d",&a,&b);
                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1480 KB Output is correct
2 Correct 0 ms 1480 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2272 KB Output is correct
2 Correct 33 ms 2272 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2404 KB Output is correct
2 Correct 9 ms 1612 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2272 KB Output is correct
2 Correct 26 ms 1744 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1480 KB Output is correct
2 Correct 29 ms 2404 KB Output is correct
3 Correct 29 ms 2404 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2404 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1612 KB Output is correct
2 Correct 59 ms 3328 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct