oj.uz

답안 #26749

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26749 2017-07-05T11:12:13 Z model_code Programming Contest (POI11_pro) C++11
20 / 100
 29 ms 2412 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Konkurs programistyczny                          *
 *   Autor:             Tomasz Idziaszek                                 *
 *   Opis:              Rozwiazanie bledne                               *
 *                      za pomoca maksymalnych skojarzen w grafie        *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#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=2*500+10;
int n,m,r,t,k;
vector<int> adj[N];
int match[N],deg[N],vis[N],prev[N];
int ans_p[N],ans_t[N],ans_d[N],ans;
int penalty;

int rek(int v)
{
   FORE(i,adj[v]) if (!vis[*i]) {
      vis[*i]=1;
      if (match[*i]==-1 || rek(match[*i])) {
	 match[v]=*i;
	 match[*i]=v;
	 return 1;
      }
   }
   return 0;
}

void matching()
{
   REP(i,n+m) match[i] = -1;
   bool change = 1;
   while (change) {
      change = 0;
      REP(j,n+m) vis[j] = 0;
      REP(j,m) if (match[j] == -1 && rek(j)) change = 1;
   }
   REP(i,m) if (match[i] != -1) {
      int pers = match[i];
      ans_t[ans] = i;
      ans_p[ans] = pers;
      ans_d[ans] = ++deg[pers];
      penalty += deg[pers]*r;
      ans++;
      adj[i].clear();
      adj[pers].erase(find(adj[pers].begin(),adj[pers].end(),i));
   }
}

int main()
{
   scanf("%d%d%d%d%d",&n,&m,&r,&t,&k);
   REP(i,k) {
      int a,b;
      scanf("%d%d",&a,&b);
      adj[m+a-1].push_back(b-1);
      adj[b-1].push_back(m+a-1);
   }
   int d = min(m,t/r);
   REP(i,d) matching();
   printf("%d %d\n", ans, penalty);
   REP(i,ans) {
      int person = ans_p[i];
      int time = --deg[person];
      printf("%d %d %d\n",person+1-m, ans_t[i]+1, time*r);
   }
}

Compilation message

pro.cpp: In function 'int main()':
pro.cpp:62: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:65: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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1224 KB It was possible to solve 95 problems and you solved only 88.

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1224 KB Output is correct
2 Incorrect 0 ms 1224 KB It was possible to get penalty of 1775900 points and you received 1877380.

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1488 KB Output is correct
2 Correct 3 ms 1488 KB Output is correct
3 Incorrect 0 ms 1224 KB It was possible to solve 121 problems and you solved only 119.

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2280 KB Output is correct
2 Correct 23 ms 2280 KB Output is correct
3 Incorrect 0 ms 1224 KB It was possible to get penalty of 1073844 points and you received 1108431.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2412 KB Output is correct
2 Correct 9 ms 1620 KB Output is correct
3 Correct 3 ms 1224 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2280 KB Output is correct
2 Correct 13 ms 1752 KB Output is correct
3 Incorrect 0 ms 1224 KB It was possible to get penalty of 114794658 points and you received 114820662.

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1488 KB It was possible to solve 390 problems and you solved only 389.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 2412 KB Output is correct
2 Correct 0 ms 1224 KB Output is correct
3 Incorrect 0 ms 1224 KB It was possible to get penalty of 2789682 points and you received 2916248.

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 1620 KB It was possible to solve 452 problems and you solved only 450.
2 Halted 0 ms 0 KB -